| Revista: | Investigación operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000379172 |
| ISSN: | 0257-4306 |
| Autores: | Suaza, Liliam R1 Arbeláez, Carlos A1 Cruz, Roberto2 |
| Instituciones: | 1Universidad de Antioquia, Facultad de Ingeniería, Medellín, Antioquia. Colombia 2Universidad de Antioquia, Facultad de Ciencias Exactas y Naturales, Medellín, Antioquia. Colombia |
| Año: | 2004 |
| Volumen: | 25 |
| Número: | 3 |
| Paginación: | 278-284 |
| País: | Cuba |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, descriptivo |
| Resumen en español | El problema 2+p-SAT aleatorio es una interpolación entre el problema de tiempo polinomial 2-SAT aleatorio, donde p=0, y el problema NP-Complet o 3- SAT aleatorio, donde p=1. Este estudio describe el costo computacional de una modificación del algoritmo TABLEAU sobre instancias 2+p-SAT aleatorias. La descripción fue obtenida por medio de experimentos con instancias 2+p-SAT aleatorias para valores de p en el intervalo 0≤p≤1, con un paso de 0.05, y valores de la variable n en el intervalo 50≤n≤8000. El costo computacional típico observado en los experimentos tuvo un comportamiento polinomial en la región definida para valores de p hasta 0.60, y un comportamiento exponencial en la región definida por p≥0.65. La región obtenida de comportamiento polinomial es significativamente más amplia que la obtenida por otros autores. Se observaron instancias extremadamente difíciles en la región 0.60≤p≤0.95. Para la región donde p≤0.50, todas las instancias no satisfacibles fueron resueltas, explorando cero ramas del árbol de búsqueda. Este último resultado sugiere que, para instancias no satisfacibles en la región p≤0.50, el algoritmo modificado TABLEAU se comporta como en instancias 2-SAT |
| Resumen en inglés | Random 2+p-SAT problem interpolates between the polynomial-time random 2-S A T problem, where p=0, and the NP-Complete random 3-SAT problem, where p=1. This study describes the computational cost of a modification of the TABLEAU algorithm over random 2+p-SAT instances. The description was achieved through experiments on random 2+p-SAT instances for values of p on the interval 0≤p≤1, with 0.05 steps and n on the interval 50≤n≤8000. The typical computational cost observed in the experiments has a polynomial behavior on the region defined by values of pup to 0.60, and an exponential behavior on the region defined by p≥0.65. The obtained region of polynomial behavior is significantly broader than the region obtained by other authors. Extremely hard instances were observed in the region 0.60≤p≤0.95. For the region p≤0.50, all the unsatisfiable instances were solved with zero explored branches on the search tree. The latter result suggests that, for unsatisfiable instances on the region p ≤ 0.50, the modified TABLEAU algorithm behaves like 2-SAT instances |
| Disciplinas: | Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Algoritmos, Estadística |
| Keyword: | Mathematics, Applied mathematics, Algorithms, Statistics |
| Texto completo: | Texto completo (Ver PDF) |
