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.
$\begingroup$
$\endgroup$
9
-
15$\begingroup$ That would be a constant fraction of all complexity papers! $\endgroup$– Mahdi CheraghchiJan 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$– JanomaJan 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$– Anthony LabarreJan 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$– Tsuyoshi ItoJan 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
|
Show 4 more comments
4 Answers
$\begingroup$
$\endgroup$
1
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$
answered Jan 20, 2012 at 15:08
-
$\begingroup$ May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$. $\endgroup$ Jan 21, 2015 at 15:55
$\begingroup$
$\endgroup$
3
$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.
answered Mar 7, 2014 at 14:36
-
1
-
$\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
$\begingroup$
$\endgroup$
2
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
answered Jan 21, 2015 at 14:57
-
$\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
$\begingroup$
$\endgroup$
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
answered Jan 21, 2015 at 18:20