3
$\begingroup$

I have in front of me 1 definition of p\poly and one of NP.

Definition of p\poly:

L E P/poly if there exists a polynomial-time Turing machine M, a polynomial p() and a function h mapping numbers to strings, where |h(n)| <= p(n), such that for all strings x, x E L <=> < x, h(|x|) > is accepted by M.

Definition of NP:

L E NP if there exists a polynomial-time Turing machine M and a polynomial p() such that for all strings x x E L <=> there exists y s.t. |y| <= p(|x|) and < x, y > is accepted by M.

What is the critical difference between the two definitions? For some x1 and x2 with |x1| = |x2| y1 and y2 might be different, but does that mean that p/poly is a subset of NP?

$\endgroup$

3 Answers 3

2
$\begingroup$

There are several "critical differences". The one immediately relevant to your final question is that, in P/poly, $h$ might not even be computable. In the case of NP, the relevant $y$ can be computed, for each $x$ (though it would take exponential time to do so), just by trying each $y$ of the appropriate length for the appropriate number of steps of M. In particular, there are only countably many languages in NP but uncountably many in P/poly.

$\endgroup$
6
$\begingroup$

The definitions that you give are very formal and tend to hide the conceptual interpretation of these complexity classes.

Imagine putting yourself in the position of the computer or Turing machine that is allowed to work for a polynomial length of time. (It's a reasonable model if you believe that people are evolved computers.) The string h in the definition of P/poly is called an advice string. You can say that it is provided by an angel who wants to help you produce the correct answer. If h could depend on the input x generally, then the angel could simply tell you the answer. So instead h only depends on the length of the input |x|.

Meanwhile in the class NP, the string y is called a proof or a certificate. It is provided by a Merlin who wants you to answer "yes" to the decision problem, whether or not it is the correct answer. It can depend on the specific input x and not just on its length |x|.

As Andreas says, a problem in P/poly does not even need to be computable. But I can mention a realistic class of problems that are in P/poly and are computable. The class BPP, which is anything computable probably correctly in polynomial time with a random number generator, is in P/poly, by a derandomization theorem. The theorem says that the angel can provide pseudorandom numbers that, together with repeated trials, make the randomized algorithm reliable as a non-randomized (but advice-dependent) algorithm.

On the the other hand, an NP-complete problem such as the Hamiltonian circuit is easily seen to fit the Merlin model. If Merlin wants to convince you that there is a Hamiltonian circuit, he only needs to show you what it is. If his certificate y isn't a Hamiltonian circuit, then you should be skeptical and answer "no".

$\endgroup$
5
$\begingroup$

A more illuminating way of thinking about P/poly than the definition you give is in terms of circuit complexity: in fact, P/poly is more like P than like NP (as its name suggests).

It is an exercise to show that for every Turing machine T that computes a function f, there is for each n a circuit (that is, an array of AND, OR and NOT gates) that takes all inputs x of length n and computes f(x). Moreover, the size of the circuit differs from the time taken by T by at most a polynomial factor.

Thus, any Turing machine can be replaced by a sequence of circuits, one for each input length. Moreover, this sequence of circuits can itself be generated by an algorithm.

If you take an arbitrary sequence of circuits (as opposed to one generated by an algorithm) taking increasing input sizes, then the resulting function is said to belong to P/poly. That is, a function in P/poly is like a function in P but without the property of uniformity -- the property that the circuits are all generated by the same algorithm. It is for that reason that you can get non-computable functions, that there are uncountably many of them, etc. etc.

The additional string in your formal definition can be thought of as encoding a circuit.

If you think about things this way it is much more obvious that the definition is not the same as that of NP.

$\endgroup$

Your Answer

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

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