5
$\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

Improve this question
$\endgroup$
4
  • 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, 2014 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.. GitHub STOP HELPING ICE
    Oct 10, 2014 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, 2014 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, 2014 at 0:40

1 Answer 1

Reset to default
34
$\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.

Improve this answer
$\endgroup$
1
  • 8
    $\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, 2014 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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