# Magic constant to solve NP-complete problem in polynomial time

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

• Scott Aaronson gave a good overview of these kinds of ideas in his Quantum Computing since Democritus: scottaaronson.com/democritus/lec7.html Commented Oct 9, 2014 at 23:19
• 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. Commented Oct 10, 2014 at 3:41
• It is not at all clear that "if P!=NP this constant can be only calculated in exponential time". $\hspace{.38 in}$ It could take something between polynomial time and exponential time. $\hspace{1.61 in}$
– user6973
Commented Oct 10, 2014 at 4:13
Probably not. What you are asking is whether NP $\subset$ P/poly. If this were true, then the polynomial hierarchy would collapse (this is the Karp–Lipton theorem), something that is widely believed not to happen.