Article ID: | iaor20117221 |
Volume: | 25 |
Issue: | 3 |
Start Page Number: | 278 |
End Page Number: | 284 |
Publication Date: | Sep 2004 |
Journal: | Revista Investigacion Operacional |
Authors: | Suaza Liliam R, Arbelaez Carlos A, Cruz Robert |
Keywords: | NP-hard |
Random 2+p-SAT problem interpolates between the polynomial-time random 2-SAT 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 ≤ 51, 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 p up 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.