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?

  • 9
    $\begingroup$ Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/… $\endgroup$ Oct 19, 2018 at 16:29
  • $\begingroup$ @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? $\endgroup$ Oct 21, 2018 at 2:12
  • 3
    $\begingroup$ @JoshuaGrochow In order to express the language as coNP, I would need first to know the polytime algorithm for NP, defeating the whole purpose. $\endgroup$ Oct 21, 2018 at 9:45

1 Answer 1


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
  if I is a valid encoding of a proof of P = NP in PA (or ZFC)
    then halt and accept

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.

  • $\begingroup$ How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ? $\endgroup$ Oct 19, 2018 at 17:03
  • $\begingroup$ @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system). $\endgroup$ Oct 19, 2018 at 18:00
  • 2
    $\begingroup$ Tall assumption. $\endgroup$ Oct 19, 2018 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 20, 2018 at 3:42
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 22, 2018 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.