<p>Here is a one:</p>

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

<p>Another one is:</p>

<p>$P \ne NP$ if and only if $P \ne PH$</p>

CC BY-SA 3.0
2015-01-21T15:55:50.627Z
May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-01-20T15:08:10.097Z
2012-01-20T16:52:01.460Z
2012-01-20T16:52:01.460Z
Mohammad Al-Turkistany
<p>$P \ne NP$ if and only if worst-case one-way functions exist.</p>

<p>Reference:</p>

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

CC BY-SA 3.0
2014-03-07T16:03:00.007Z
a ref would be good
vzn
CC BY-SA 3.0
2014-03-07T16:09:47.187Z
Are you sure? I hadn't heard of worst-case OWFs before, but from the notes [here](http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture3.pdf) it looks like their existence is equivalent to $BPP \neq NP$.
Huck Bennett
CC BY-SA 3.0
2014-03-07T17:47:45.453Z
Yes I am sure. :) See the reference.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-03-07T14:36:54.840Z
2014-03-07T17:46:54.270Z
2014-03-07T17:46:54.270Z
Mohammad Al-Turkistany
<p>Here is a result from descriptive complexity theory:</p>

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

<p>Reference:
Immerman, <a href="http://people.cs.umass.edu/~immerman/pub/LanguagesWhichSTOC83.pdf">Languages that capture complexity classes</a></p>

CC BY-SA 3.0
2015-01-21T15:59:04.007Z
... on ordered structures. Otherwise we know unconditionally that such properties exist.
Emil Jeřábek
CC BY-SA 3.0
2015-01-21T16:10:07.193Z
@EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-01-21T14:57:30.110Z
2015-01-21T14:57:30.110Z
Mohammad Al-Turkistany
<p>Ladner theorem can be stated as:</p>

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

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

<p>Reference</p>

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

CC BY-SA 3.0
2015-01-21T18:20:05.410Z
2015-01-21T18:20:05.410Z
Mohammad Al-Turkistany
<p>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. <br></p>

CC BY-SA 3.0
2012-01-19T19:17:51.477Z
That would be a constant fraction of all complexity papers!
Mahdi Cheraghchi
CC BY-SA 3.0
2012-01-19T19:37:35.017Z
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
CC BY-SA 3.0
2012-01-19T22:58:39.217Z
@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
CC BY-SA 3.0
2012-01-19T23:43:29.813Z
@AnthonyLabarre: I said "list of conditions **implying** P?NP", not **implied by** P?NP. That is, a list of statements of the form "**If** [condition], **then** P=NP" or "**If** [condition], **then** P!=NP". The idea, as I hinted, is to avoid "listing the many consequences of this result" (P=NP or P!=NP).
Janoma
CC BY-SA 3.0
2012-01-20T00:32:08.237Z
@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
CC BY-SA 3.0
2012-01-20T01:10:32.837Z
@Tsuyoshilto: true, but I guess many of the problems will fall under a same category (e.g. for any NP-complete problem *X* we can say "If *X* is solvable in polynomial time, then P=NP"). Still, given these observations, I'd say that a better question (for a wiki, perhaps), would be maintaining a list of statements directly implied by or implying one of the outcomes of P?NP, not in the philosophical, "Impagliazzo's Worlds" sense, but in a more "mathematical" (for lack of a better word) fashion (for example: "if P=NP then there are polynomial-time algorithms for problems X, Y and Z").
Janoma
CC BY-SA 3.0
2012-01-20T02:39:01.043Z
@Janoma: "If X then P=NP" is the same as "If P≠NP then not-X".
Jeffε
CC BY-SA 3.0
2012-01-20T15:52:39.630Z
a well known open, apparently stronger conjecture than $\mathsf{P} \neq \mathsf{NP}$ is that there are no polynomial-sized circuits over the complete basis (AND,OR,NOT gates) to solve $\mathsf{NP}$-complete problems. but it is not known if $\mathsf{P} \neq \mathsf{NP}$ implies that such circuits dont exist.
vzn
CC BY-SA 3.0
2012-01-20T17:05:55.657Z
this doesn't seem like a real question, but a list. I think this is considered off-topic now that we can't make 'community wiki' questions. Although I think such a resource would be useful, I am not sure if cstheory is the best way to produce such a resource.
Artem Kaznatcheev
<cc.complexity-theory><big-list><p-vs-np>
List of theorems stating that P does not equal NP if and only if
Tayfun Pay
# List of theorems stating that P does not equal NP if and only if

(Asked by: username_0 on 2012-01-19)

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.

**Tags:** cc.complexity-theory, big-list, p-vs-np

> **Comments:**
> **username_1**: That would be a constant fraction of all complexity papers!  
> **username_2**: 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.  
> **username_3**: @username_2: 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.  
> **username_2**: @AnthonyLabarre: I said "list of conditions **implying** P?NP", not **implied by** P?NP. That is, a list of statements of the form "**If** [condition], **then** P=NP" or "**If** [condition], **then** P!=NP". The idea, as I hinted, is to avoid "listing the many consequences of this result" (P=NP or P!=NP).  
> **username_4**: @username_2: 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.  
> **username_2**: @Tsuyoshilto: true, but I guess many of the problems will fall under a same category (e.g. for any NP-complete problem *X* we can say "If *X* is solvable in polynomial time, then P=NP"). Still, given these observations, I'd say that a better question (for a wiki, perhaps), would be maintaining a list of statements directly implied by or implying one of the outcomes of P?NP, not in the philosophical, "Impagliazzo's Worlds" sense, but in a more "mathematical" (for lack of a better word) fashion (for example: "if P=NP then there are polynomial-time algorithms for problems X, Y and Z").  
> **username_5**: @username_2: "If X then P=NP" is the same as "If P≠NP then not-X".  
> **username_6**: a well known open, apparently stronger conjecture than $\mathsf{P} \neq \mathsf{NP}$ is that there are no polynomial-sized circuits over the complete basis (AND,OR,NOT gates) to solve $\mathsf{NP}$-complete problems. but it is not known if $\mathsf{P} \neq \mathsf{NP}$ implies that such circuits dont exist.  
> **username_7**: this doesn't seem like a real question, but a list. I think this is considered off-topic now that we can't make 'community wiki' questions. Although I think such a resource would be useful, I am not sure if cstheory is the best way to produce such a resource.  

---

## 4 answers

### Answer by username_8 on 2012-01-20. Score: 11

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$

> **Comments:**
> **username_8**: May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$.  

---

### Answer by username_8 on 2014-03-07. Score: 11

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

> **Comments:**
> **username_6**: a ref would be good  
> **username_9**: Are you sure? I hadn't heard of worst-case OWFs before, but from the notes [here](http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture3.pdf) it looks like their existence is equivalent to $BPP \neq NP$.  
> **username_8**: Yes I am sure. :) See the reference.  

---

### Answer by username_8 on 2015-01-21. Score: 8

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](http://people.cs.umass.edu/~immerman/pub/LanguagesWhichSTOC83.pdf)

> **Comments:**
> **username_10**: ... on ordered structures. Otherwise we know unconditionally that such properties exist.  
> **username_8**: @EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper.  

---

### Answer by username_8 on 2015-01-21. Score: 7

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


---

