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$
  • 15
    $\begingroup$ That would be a constant fraction of all complexity papers! $\endgroup$ – MCH Jan 19 '12 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 '12 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$ – Anthony Labarre Jan 19 '12 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$ – Tsuyoshi Ito Jan 20 '12 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 '12 at 2:39
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$
  • $\begingroup$ May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$. $\endgroup$ – Mohammad Al-Turkistany Jan 21 '15 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$
  • 1
    $\begingroup$ a ref would be good $\endgroup$ – vzn Mar 7 '14 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$ – Huck Bennett Mar 7 '14 at 16:09
  • $\begingroup$ Yes I am sure. :) See the reference. $\endgroup$ – Mohammad Al-Turkistany Mar 7 '14 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$
  • $\begingroup$ ... on ordered structures. Otherwise we know unconditionally that such properties exist. $\endgroup$ – Emil Jeřábek supports Monica Jan 21 '15 at 15:59
  • $\begingroup$ @EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper. $\endgroup$ – Mohammad Al-Turkistany Jan 21 '15 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, privacy policy and cookie policy

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