# 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 Sep 9 '14 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. – Marzio De Biasi Sep 9 '14 at 7:11
• How about if it is provable in HoTT but not ZFC? – Chad Brewbaker Sep 9 '14 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). – Phylliida Sep 9 '14 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. – Phylliida Sep 9 '14 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).