<p>If you assume that <span class="math-container">$P=^?NP$</span> is provable in PA (or ZFC), a trivial example is the following:</p>

<pre><code>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
</code></pre>

<p>Another - less trivial - example that relies on no assumption is the following:</p>

<pre><code>Input: x   (boolean formula)
Find the minimum i such that
  1) |M_i| &lt; log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration] 
  2) and  M_i solves SAT correctly 
       on all formulas |y| &lt; 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.
</code></pre>

<p>If <span class="math-container">$P =NP$</span> the algorithm will soon or later - suppose on input <span class="math-container">$x_0$</span> - find the index of the polynomial time Turing machine (or a padded version of it) <span class="math-container">$M_{SAT}$</span> that solves SAT in <span class="math-container">$O( |x| ^ { |M_{SAT}| })$</span> and for all inputs greater than <span class="math-container">$x_0$</span> 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 <span class="math-container">$P = NP$</span> the algorithm solves SAT in polynomial time on all but a finite number of instances.</p>

<p>If <span class="math-container">$P \neq NP$</span> the algorithm runs in exponential time.</p>

CC BY-SA 4.0
2018-10-19T17:03:49.787Z
How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
user2925716
CC BY-SA 4.0
2018-10-19T18:00:17.583Z
@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
CC BY-SA 4.0
2018-10-19T19:24:50.780Z
Tall assumption.
Jirka Hanika
CC BY-SA 4.0
2018-10-19T19:51:25.680Z
This runs in polynomial time in either case.
Joshua
CC BY-SA 4.0
2018-10-19T19:56:35.960Z
@Joshua: why? If P<>NP the algorithm will never find a proof so it will loop between 1 and N on every input (notice that the input is in binary so it's length is $log_2(N)$)
Marzio De Biasi
CC BY-SA 4.0
2018-10-19T20:05:56.017Z
Oh that makes it worse. It's O(1) if P=NP and O(2^N) otherwise, but we can trivially fix it to O(1) on either side if we assume P=?NP is not independent of axioms.
Joshua
CC BY-SA 4.0
2018-10-20T03:42:40.157Z
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
CC BY-SA 4.0
2018-10-21T06:57:15.170Z
Are there no "practical" examples, that is algorithms that may actually be used rather then ones deliberately contrived to show the point?
Nathaniel Bubis
CC BY-SA 4.0
2018-10-22T10:24:11.197Z
@DmytroTaranovsky: a clarification, what is *i.o.*-exponential ?
Marzio De Biasi
CC BY-SA 4.0
2018-10-22T13:01:23.040Z
The claim that the second algorithm runs in exponential time if $P\ne NP$ is unjustified, and most likely wrong. For example, assume that $P\ne NP$, but $NP\subseteq P/o(n)$. Then for any $n=|x|$, there exists a TM $M_i$ of length $|M_i|<\log\log|x|$ that computes SAT correctly on all inputs $|y|<\log\log|x|$, rejects all longer inputs, and does all this in time $(\log\log|x|)^c$ (independent of the length of its input). If this $M_i$ is the one picked up by the loop, the algorithm will halt (reject) in time $n+2^{O((\log\log n)^c)}=n+o(n)$ or so. Now, it is possible that the loop happens ...
Emil Jeřábek
CC BY-SA 4.0
2018-10-22T13:03:56.617Z
... to find another TM $M_j$ with $j<i$ that also works correctly on inputs $|y|<\log\log|x|$, and that happens to take an enormous time on input $x$. However, I see no guarantee for the latter behaviour, and as far as I can see, it is conceivable that the former behaviour will prevail for all or most $n$.
Emil Jeřábek
CC BY-SA 4.0
2018-10-22T15:19:03.327Z
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
CC BY-SA 4.0
2018-10-22T15:33:57.453Z
@EmilJeřábek: we could check $|M_i| < \log \log \log |x|$ on $|y| < \log \log |x|$.
Marzio De Biasi
CC BY-SA 4.0
2018-10-22T16:58:54.327Z
This rules out the specific scenario I brought up in my comment, but I don’t see how it would fix the actual problem.
Emil Jeřábek
CC BY-SA 4.0
2018-11-01T15:07:47.033Z
Could you include in your answer your comment with correct mathjax from here? https://blog.computationalcomplexity.org/2018/10/if-pnp-then-we-have-alg-for-sat.html?showComment=1540820172336#c2698850165138217415 I haven't managed to understand it, and it's quite hard to continue the discussion on a moderated blog.
domotorp
CC BY-SA 4.0
2018-10-19T17:00:52.873Z
2018-10-20T00:28:06.700Z
2018-10-20T00:28:06.700Z
Marzio De Biasi
<p>Is there a known, explicit example of an algorithm with the property such that if <span class="math-container">$P\neq NP$</span> then this algorithm doesn't run in polynomial time and if <span class="math-container">$P=NP$</span> then it does run in polynomial time?</p>

CC BY-SA 4.0
2018-10-19T16:29:35.293Z
Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time *on accepting instances* https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms
Emil Jeřábek
CC BY-SA 4.0
2018-10-21T02:12:12.193Z
@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
CC BY-SA 4.0
2018-10-21T09:45:46.887Z
@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
<ds.algorithms><np><p-vs-np>
Algorithm whose running time depends on P vs. NP
user2925716
# Algorithm whose running time depends on P vs. NP

(Asked by: username_0 on 2018-10-19)

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?

**Tags:** ds.algorithms, np, p-vs-np
> **Comments:**
> **username_1**: Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time *on accepting instances* https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms  
> **username_2**: @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?  
> **username_1**: @JoshuaGrochow In order to express the language as coNP, I would need first to *know* the polytime algorithm for NP, defeating the whole purpose.  

---

## 1 answers

### Answer by username_3 on 2018-10-19. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_0**: How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?  
> **username_3**: @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).  
> **username_4**: Tall assumption.  
> **username_5**: This runs in polynomial time in either case.  
> **username_3**: @Joshua: why? If P<>NP the algorithm will never find a proof so it will loop between 1 and N on every input (notice that the input is in binary so it's length is $log_2(N)$)  
> **username_5**: Oh that makes it worse. It's O(1) if P=NP and O(2^N) otherwise, but we can trivially fix it to O(1) on either side if we assume P=?NP is not independent of axioms.  
> **username_6**: 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.  
> **username_7**: Are there no "practical" examples, that is algorithms that may actually be used rather then ones deliberately contrived to show the point?  
> **username_3**: @DmytroTaranovsky: a clarification, what is *i.o.*-exponential ?  
> **username_1**: The claim that the second algorithm runs in exponential time if $P\ne NP$ is unjustified, and most likely wrong. For example, assume that $P\ne NP$, but $NP\subseteq P/o(n)$. Then for any $n=|x|$, there exists a TM $M_i$ of length $|M_i|<\log\log|x|$ that computes SAT correctly on all inputs $|y|<\log\log|x|$, rejects all longer inputs, and does all this in time $(\log\log|x|)^c$ (independent of the length of its input). If this $M_i$ is the one picked up by the loop, the algorithm will halt (reject) in time $n+2^{O((\log\log n)^c)}=n+o(n)$ or so. Now, it is possible that the loop happens ...  
> **username_1**: ... to find another TM $M_j$ with $j<i$ that also works correctly on inputs $|y|<\log\log|x|$, and that happens to take an enormous time on input $x$. However, I see no guarantee for the latter behaviour, and as far as I can see, it is conceivable that the former behaviour will prevail for all or most $n$.  
> **username_6**: 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.  
> **username_3**: @EmilJeřábek: we could check $|M_i| < \log \log \log |x|$ on $|y| < \log \log |x|$.  
> **username_1**: This rules out the specific scenario I brought up in my comment, but I don’t see how it would fix the actual problem.  
> **username_8**: Could you include in your answer your comment with correct mathjax from here? https://blog.computationalcomplexity.org/2018/10/if-pnp-then-we-have-alg-for-sat.html?showComment=1540820172336#c2698850165138217415 I haven't managed to understand it, and it's quite hard to continue the discussion on a moderated blog.  

---

