# List of theorems stating that P does not equal NP if and only if

I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on and so forth.

• That would be a constant fraction of all complexity papers! – Mahdi Cheraghchi Jan 19 '12 at 19:17
• I would say: "list of conditions implying P?NP", since not all those theorems are "if and only if". Also, I guess people are more interested --in general-- in knowing how to prove P?NP by proving something else, than in listing the many consequences of this result, a topic that has been widely discussed elsewhere. – Janoma Jan 19 '12 at 19:37
• @Janoma: if you want to restrict yourself to implications, then the list will be really huge, given the enormous amount of results of the form: "If P!=NP, then problem X cannot be solved exactly / approximated within a constant factor in polynomial time". The question should be much more focused or better stated if we want to avoid that. – Anthony Labarre Jan 19 '12 at 22:58
• @Janoma: That does not solve Anthony’s well-founded concern. Hypotheses which imply P=NP are simply negations of consequences of P≠NP, and hypotheses which imply P≠NP are negations of consequences of P=NP. If SAT is solvable in polynomial time, then P=NP. If Max3SAT is polynomial-time approximable within a constant factor less than 8/7, then P=NP. And so on. – Tsuyoshi Ito Jan 20 '12 at 0:32
• @Janoma: "If X then P=NP" is the same as "If P≠NP then not-X". – Jeffε Jan 20 '12 at 2:39

Here is a one:

Mahaney's Theorem: There is no sparse NP-complete set if and only if $P \ne NP$
(under Karp reduction).

Another one is:

$P \ne NP$ if and only if $P \ne PH$

• May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$. – Mohammad Al-Turkistany Jan 21 '15 at 15:55

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

• a ref would be good – vzn Mar 7 '14 at 16:03
• Are you sure? I hadn't heard of worst-case OWFs before, but from the notes here it looks like their existence is equivalent to $BPP \neq NP$. – Huck Bennett Mar 7 '14 at 16:09
• Yes I am sure. :) See the reference. – Mohammad Al-Turkistany Mar 7 '14 at 17:47

Here is a result from descriptive complexity theory:

$P \ne NP$ if and only if some second order property is not expressible using first order logic plus least fixed point.

Reference: Immerman, Languages that capture complexity classes

• ... on ordered structures. Otherwise we know unconditionally that such properties exist. – Emil Jeřábek Jan 21 '15 at 15:59
• @EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper. – Mohammad Al-Turkistany Jan 21 '15 at 16:10

Ladner theorem can be stated as:

$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.

Incomplete set is a set that is not complete for $NP$ under many-one polynomial time reductions.

Reference

Complexity Theory and Cryptology: An Introduction to Cryptocomplexity By Jörg Rothe, page 106