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

Toby Walsh, University College Cork

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.