<p>Probably not. What you are asking is whether NP $\subset$ <a href="https://en.wikipedia.org/wiki/P/poly">P/poly</a>. If this were true, then the polynomial hierarchy would collapse (this is the <a href="https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem">Karp–Lipton theorem</a>), something that is widely believed not to happen.</p>

CC BY-SA 3.0
2014-10-10T10:30:40.447Z
To expand a little, such a universal constant is called (polynomial) advice, and the class of languages which are decidable in polynomial time with access to polynomial advice is called P/poly.
Max
CC BY-SA 3.0
2014-10-09T23:07:36.123Z
2014-10-09T23:07:36.123Z
David Eppstein
<p>Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial length $P(n)$?
Clearly, if $P\ne NP$ this constant can be only calculated in exponential time and the calculation must be done for each $n$.</p>

<p>Thanks</p>

CC BY-SA 3.0
2014-10-09T23:19:47.433Z
Scott Aaronson gave a good overview of these kinds of ideas in his Quantum Computing since Democritus: http://www.scottaaronson.com/democritus/lec7.html
Phylliida
CC BY-SA 3.0
2014-10-10T03:41:00.497Z
If you're only looking at inputs of size n, everything is O(1), with the constant just being the maximum runtime over the (finite) set of inputs.
R.. GitHub STOP HELPING ICE
<time-complexity><polynomial-time><np-complete>
Magic constant to solve NP-complete problem in polynomial time
Juggernaut
# Magic constant to solve NP-complete problem in polynomial time

(Asked by: username_0 on 2014-10-09)

Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C\_n$ that has a polynomial length $P(n)$?
Clearly, if $P\ne NP$ this constant can be only calculated in exponential time and the calculation must be done for each $n$.

Thanks

**Tags:** time-complexity, polynomial-time, np-complete
> **Comments:**
> **username_1**: Scott Aaronson gave a good overview of these kinds of ideas in his Quantum Computing since Democritus: http://www.scottaaronson.com/democritus/lec7.html  
> **username_2**: If you're only looking at inputs of size n, everything is O(1), with the constant just being the maximum runtime over the (finite) set of inputs.  

---

## 1 answers

### Answer by username_3 on 2014-10-09. Score: 34

Probably not. What you are asking is whether NP $\subset$ [P/poly](https://en.wikipedia.org/wiki/P/poly). If this were true, then the polynomial hierarchy would collapse (this is the [Karp–Lipton theorem](https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem)), something that is widely believed not to happen.

> **Comments:**
> **username_4**: To expand a little, such a universal constant is called (polynomial) advice, and the class of languages which are decidable in polynomial time with access to polynomial advice is called P/poly.  

---

