4
$\begingroup$

I am looking for nontrivial examples of complexity class separations that are known to follow from the P!=NP hypothesis. By a "nontrivial example" I mean that it is not just an automatic consequence of an easy containment relationship, such as P!=PSPACE, P!=PH etc. would be.

$\endgroup$
5
$\begingroup$

De Loera, Lee, Malkin, and Margulies developed an algorithm for determining infeasibility of certain combinatorial problems using Hilbert's Nullstellensatz.

For example, they take the constraints of 3-coloring a graph and describe that problem as a system of polynomial equations. They compute a set of certificate polynomials which verify that these polynomials have no solutions (using the Nullstellensatz). To make this computation finite, they bound the degree of the certificates. For the 3-coloring case, they were unable to find a non-3-colorable graph which required degree higher than four for the certificate.

If P $\neq$ NP, then P $\neq$ coNP and the degree of a Nullstellensatz Certificate for this problem is unbounded, as a finite bound would yield a polynomial-time algorithm.

$\endgroup$
  • $\begingroup$ I'm a bit lost. Why is $P \neq co-NP$ necessary for this to be a poly-time algorithm. $\endgroup$ – Opt Nov 18 '10 at 16:22
  • $\begingroup$ The algorithm is trying to solve a coNP-complete language "NOT-3COLORABLE". If the degree is bounded by a constant, then this algorithm is poly-time and P = coNP = NP. $\endgroup$ – Derrick Stolee Nov 18 '10 at 16:37
5
$\begingroup$

Two major nontrivial consequences of $P\ne NP$:

  • Ladner Theorem: There is infinite number of sets in $NP$ that are neither in $P$ nor $NP$-complete under Karp reductions.
  • Shaffer Dichotomy Theorem: All Boolean Constraint satisfaction problems (over $\{0,1\}^*$) are either in $P$ or $NP$-complete.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy