6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Scott Aaronson gave a good overview of these kinds of ideas in his Quantum Computing since Democritus: scottaaronson.com/democritus/lec7.html $\endgroup$ – Phylliida Oct 9 '14 at 23:19
  • $\begingroup$ 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. $\endgroup$ – R.. Oct 10 '14 at 3:41
  • 3
    $\begingroup$ 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}$ $\endgroup$ – user6973 Oct 10 '14 at 4:13
  • $\begingroup$ This may answer your question UNIVERSAL EQUATION - Proof of P=NP academia.edu/8809357/UNIVERSAL_EQUATION_-_Proof_of_P_NP $\endgroup$ – user25495 Oct 17 '14 at 0:40
33
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Max Oct 10 '14 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.