The Interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Satisfiability

We study in detail the interface between P and NP by means of five new problem classes. Like the well known 2+p-SAT problem, these new problems smoothly interpolate between P and NP by mixing together a polynomial and a NP-complete problem. In many cases, the polynomial subproblem can dominate the problem’s satisfiability and the search complexity. However, this is not always the case, and understanding why remains a very interesting open question. We identify phase transition behavior in each of these problem classes. Surprisingly we observe transitions with both smooth and sharp regions. Finally we show how these problem classes can help to understand algorithm behavior by considering search trajectories through the phase space.