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?

  • 8
    $\begingroup$ Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/… $\endgroup$ – Emil Jeřábek Oct 19 '18 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$ – Joshua Grochow Oct 21 '18 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$ – Emil Jeřábek Oct 21 '18 at 9:45
  • $\begingroup$ @Emil: ah, right, good. Thanks. $\endgroup$ – 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
  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$ – user2925716 Oct 19 '18 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$ – Marzio De Biasi Oct 19 '18 at 18:00
  • 2
    $\begingroup$ Tall assumption. $\endgroup$ – Jirka Hanika Oct 19 '18 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$ – Dmytro Taranovsky Oct 20 '18 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$ – Dmytro Taranovsky Oct 22 '18 at 15:19

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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