<p>I recall Scott Aaronson making the claim that either $P\neq NP$ or he has superpowers.</p>

<p>What reason is there, if any, to believe that it is not the case that any decision procedure has constants (or exponents) that would make an ultrafinitist squirm?</p>

<p>That is to say, if I take "has superpowers" to mean "is capable of <em>practically</em> deciding reasonably sized pathological instances of <em>insert NP-complete problem here</em>", why should I believe that there isn't a third option?</p>

CC BY-SA 3.0
2014-06-13T02:21:30.240Z
This is exactly Don Knuth's belief: http://www.informit.com/articles/article.aspx?p=2213858
GMB
CC BY-SA 3.0
2014-06-13T05:13:27.237Z
To answer the title question: Nothing. We know nothing about lower bounds.
Jeffε
<p-vs-np>
What is known about lower bounds on the algorithm if P=NP
Alex R
# What is known about lower bounds on the algorithm if P=NP

(Asked by: username_0 on 2014-06-13)

I recall Scott Aaronson making the claim that either $P\neq NP$ or he has superpowers.

What reason is there, if any, to believe that it is not the case that any decision procedure has constants (or exponents) that would make an ultrafinitist squirm?

That is to say, if I take "has superpowers" to mean "is capable of *practically* deciding reasonably sized pathological instances of *insert NP-complete problem here*", why should I believe that there isn't a third option?

**Tags:** p-vs-np
> **Comments:**
> **username_1**: This is exactly Don Knuth's belief: http://www.informit.com/articles/article.aspx?p=2213858  
> **username_2**: To answer the title question: Nothing. We know nothing about lower bounds.  

---

## 0 answers

