A New Class of Hard 3-SAT Instances
Marko Žnidarič · arXiv (Cornell University) · 2005
We identify a new class of hard 3-SAT instances, namely a random 3-SAT problems having exactly one solution and as few clauses as possible. It is numerically shown that the running time of complete methods as well as of local search algorithms for such problems is larger than for random instances around the phase transition point. We therefore provide instances with an exponential complexity in the so-called “easy ” region, below the critical value of m/n. This puts a new light on the connection between the phase transition phenomenon and NP-completeness.