# Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $$P\neq NP$$ then this algorithm doesn't run in polynomial time and if $$P=NP$$ then it does run in polynomial time?

• Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/… – Emil Jeřábek Oct 19 '18 at 16:29
• @Emil: if P=NP then also P=coNP, so can't you simultaneously do Levin search on the complement of your language, thus giving a truly poly time algorithm on all instances? – Joshua Grochow Oct 21 '18 at 2:12
• @JoshuaGrochow In order to express the language as coNP, I would need first to know the polytime algorithm for NP, defeating the whole purpose. – Emil Jeřábek Oct 21 '18 at 9:45
• @Emil: ah, right, good. Thanks. – Joshua Grochow Oct 21 '18 at 14:19

If you assume that $$P=^?NP$$ is provable in PA (or ZFC), a trivial example is the following:

Input: N   (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject


Another - less trivial - example that relies on no assumption is the following:

Input: x   (boolean formula)
Find the minimum i such that
1) |M_i| < log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration]
2) and  M_i solves SAT correctly
on all formulas |y| < log(log(|x|))
halting in no more than |y|^|M_i| steps
[ checkable in polynomial time w.r.t. |x| ]
if such i exists simulate M_i on input x
until it stops and accept/reject according to its output
or until it reaches 2^|x| steps and in this case reject;
if such i doesn't exist loop for 2^|x| steps and reject.


If $$P =NP$$ the algorithm will soon or later - suppose on input $$x_0$$ - find the index of the polynomial time Turing machine (or a padded version of it) $$M_{SAT}$$ that solves SAT in $$O( |x| ^ { |M_{SAT}| })$$ and for all inputs greater than $$x_0$$ will continue to simulate it and halt in polynomial time (note that step 2 can also be checked in polynomial time). In other words if $$P = NP$$ the algorithm solves SAT in polynomial time on all but a finite number of instances.

If $$P \neq NP$$ the algorithm runs in exponential time.

• How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ? – user2925716 Oct 19 '18 at 17:03
• @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system). – Marzio De Biasi Oct 19 '18 at 18:00
• Tall assumption. – Jirka Hanika Oct 19 '18 at 19:24
• If P≠NP, the runtime of the unconditional algorithm is superpolynomial (as requested), but if NP is only very slightly superpolynomial, not exponential. We can change the algorithm to make it i.o.-exponential, but provably making it exponential (as opposed to just i.o.-exponential) if P≠NP is likely as hard as solving P=NP. – Dmytro Taranovsky Oct 20 '18 at 3:42
• I used i.o.-exponential to mean exponential for infinitely many input sizes; i.o.-exponential can still oscillate between exponential and non-exponential as input size changes. Also, Emil Jeřábek's comment appears correct; a fix to provably get superpolynomial time (if P≠NP) is to always use at least $x^{|M_i|}$ time; and for i.o.-exponential -- at least $2^x$ each time we increase i. – Dmytro Taranovsky Oct 22 '18 at 15:19