<p>If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0_2$, it is not known to be $\Sigma^0_2$, and this is outright false in the relativized world (see <a href="https://cstheory.stackexchange.com/a/16644">https://cstheory.stackexchange.com/a/16644</a>).</p>

CC BY-SA 3.0
2014-09-10T22:16:05.140Z
Related: [Emil's comment on MO](http://mathoverflow.net/questions/57345/examples-of-g-delta-sets/57348#comment144034_57348)
Kaveh
CC BY-SA 3.0
2014-09-10T15:20:18.073Z
2014-09-10T15:20:18.073Z
2017-04-13T12:32:28.167Z
Emil Jeřábek
<p>Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time?</p>

<p>A simple example would be: If P!=NP, compute a primality test for a random n-bit number, otherwise, evaluate a random worst-case position in <a href="http://en.wikipedia.org/wiki/Generalized_game">generalized</a> chess of a nxn board with 2n pieces on each side. That seems kinda hacky though. Are there any more natural examples?</p>

CC BY-SA 3.0
2014-09-09T03:54:38.713Z
Not exactly what you're asking about, but there are connections between circuit lower bounds (e.g. SAT requires super-polynomial size circuits, implying particularly that P != NP) and derandomization (e.g. BPP = P, in particular some new problems would be known to be in P). But I'm pretty sure that P!=NP is not a strong enough assumption for any such result.
usul
CC BY-SA 3.0
2014-09-09T07:11:15.910Z
If $P\neq NP$ is provable in ZFC (open problem) then an algorithm could be: on input $x$, if $x$ doesn't encode a valid proof of $P\neq NP$ then ouput $0$ otherwise simulate the Turing machine $x$ on empty tape for $2^{|x|}$ steps and output $0$ if it rejects or doesn't halt, $1$ otherwise.
Marzio De Biasi
CC BY-SA 3.0
2014-09-09T11:49:03.970Z
How about if it is provable in HoTT but not ZFC?
Chad Brewbaker
CC BY-SA 3.0
2014-09-09T19:52:14.623Z
@MarzioDeBiasi That's true, thanks, and really as Chad pointed out you could use any set of axioms in place of ZFC, hopefully using a consistent one that can prove in a meaningful way that P!=NP. That still feels pretty hacky though, I mean like my example we could easily replace the $2^[|x|]$ with any other desired time complexity (including, say, solving the halting problem).
Phylliida
CC BY-SA 3.0
2014-09-09T19:53:50.283Z
It's possible there are no natural looking examples of the type I'm asking for, but it seems like formal definitions of "natural" (say, high probability of picking this problem given a random problem in all problems in EXP) sorta lose out on some of the meaning so it might not be that meaningful to try and prove that, I'm not sure.
Phylliida
<cc.complexity-theory><reference-request>
Problem that is in P only if P!=NP
Phylliida
# Problem that is in P only if P!=NP

(Asked by: username_0 on 2014-09-09)

Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time?

A simple example would be: If P!=NP, compute a primality test for a random n-bit number, otherwise, evaluate a random worst-case position in [generalized](http://en.wikipedia.org/wiki/Generalized_game) chess of a nxn board with 2n pieces on each side. That seems kinda hacky though. Are there any more natural examples?

**Tags:** cc.complexity-theory, reference-request

> **Comments:**
> **username_1**: Not exactly what you're asking about, but there are connections between circuit lower bounds (e.g. SAT requires super-polynomial size circuits, implying particularly that P != NP) and derandomization (e.g. BPP = P, in particular some new problems would be known to be in P). But I'm pretty sure that P!=NP is not a strong enough assumption for any such result.  
> **username_2**: If $P\neq NP$ is provable in ZFC (open problem) then an algorithm could be: on input $x$, if $x$ doesn't encode a valid proof of $P\neq NP$ then ouput $0$ otherwise simulate the Turing machine $x$ on empty tape for $2^{|x|}$ steps and output $0$ if it rejects or doesn't halt, $1$ otherwise.  
> **username_3**: How about if it is provable in HoTT but not ZFC?  
> **username_0**: @MarzioDeBiasi That's true, thanks, and really as Chad pointed out you could use any set of axioms in place of ZFC, hopefully using a consistent one that can prove in a meaningful way that P!=NP. That still feels pretty hacky though, I mean like my example we could easily replace the $2^[|x|]$ with any other desired time complexity (including, say, solving the halting problem).  
> **username_0**: It's possible there are no natural looking examples of the type I'm asking for, but it seems like formal definitions of "natural" (say, high probability of picking this problem given a random problem in all problems in EXP) sorta lose out on some of the meaning so it might not be that meaningful to try and prove that, I'm not sure.  

---

## 1 answers

### Answer by username_4 on 2014-09-10. Score: 15 | Accepted answer

If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0\_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0\_2$, it is not known to be $\Sigma^0\_2$, and this is outright false in the relativized world (see <https://cstheory.stackexchange.com/a/16644>).

> **Comments:**
> **username_5**: Related: [Emil's comment on MO](http://mathoverflow.net/questions/57345/examples-of-g-delta-sets/57348#comment144034_57348)  

---

