ANÁLISIS EXPERIMENTAL DEL COSTO COMPUTACIONAL DEL PROBLEMA 2+p-SAT ALEATORIO

Abstract

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 ≤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 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