# 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 – Phylliida Oct 9 '14 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. – R.. GitHub STOP HELPING ICE Oct 10 '14 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 Oct 10 '14 at 4:13
• This may answer your question UNIVERSAL EQUATION - Proof of P=NP academia.edu/8809357/UNIVERSAL_EQUATION_-_Proof_of_P_NP – user25495 Oct 17 '14 at 0:40

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.