18
$\begingroup$

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.

$\endgroup$
9
  • 15
    $\begingroup$ That would be a constant fraction of all complexity papers! $\endgroup$ 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
    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$ 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$ 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ε
    Jan 20, 2012 at 2:39

4 Answers 4

11
$\begingroup$

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$

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

$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.

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

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

$\endgroup$
2
  • $\begingroup$ ... on ordered structures. Otherwise we know unconditionally that such properties exist. $\endgroup$ Jan 21, 2015 at 15:59
  • $\begingroup$ @EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper. $\endgroup$ Jan 21, 2015 at 16:10
7
$\begingroup$

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

$\endgroup$

Your Answer

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

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