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.

  • 15
    $\begingroup$ That would be a constant fraction of all complexity papers! $\endgroup$ Commented Jan 19, 2012 at 19:17
  • 5
    $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Jan 19, 2012 at 19:37
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Jan 19, 2012 at 22:58
  • 4
    $\begingroup$ @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. $\endgroup$ Commented Jan 20, 2012 at 0:32
  • 7
    $\begingroup$ @Janoma: "If X then P=NP" is the same as "If P≠NP then not-X". $\endgroup$
    – Jeffε
    Commented Jan 20, 2012 at 2:39

4 Answers 4


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$

  • $\begingroup$ May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$. $\endgroup$ Commented Jan 21, 2015 at 15:55

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


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

  • 1
    $\begingroup$ a ref would be good $\endgroup$
    – vzn
    Commented Mar 7, 2014 at 16:03
  • $\begingroup$ 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$. $\endgroup$ Commented Mar 7, 2014 at 16:09
  • $\begingroup$ Yes I am sure. :) See the reference. $\endgroup$ Commented Mar 7, 2014 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

  • $\begingroup$ ... on ordered structures. Otherwise we know unconditionally that such properties exist. $\endgroup$ Commented Jan 21, 2015 at 15:59
  • $\begingroup$ @EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper. $\endgroup$ Commented Jan 21, 2015 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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.