# Problem that is in P only if P!=NP

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 chess of a nxn board with 2n pieces on each side. That seems kinda hacky though. Are there any more natural examples?

• 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
Commented Sep 9, 2014 at 3:54
• 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. Commented Sep 9, 2014 at 7:11
• How about if it is provable in HoTT but not ZFC? Commented Sep 9, 2014 at 11:49
• @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). Commented Sep 9, 2014 at 19:52
• 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. Commented Sep 9, 2014 at 19:53

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