# p\poly and NP definitions

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?

-

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.

-

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.

-