My textbook claims: P \subset P/Poly, and that this is proper.

It claims that all unary languages are in P/Poly, and then goes on to claim that UHALT = {1^n | n encodes (M,x) s.t. M halts on x } is in P/Poly, but not in P.

I understand the following thing:

```
(1) HALT can not be calculated by any TM
(2) UHALT can not be calculated by any TM
(3) Clearly, HALT \not\in P
(4) P/Poly is non-uniform; i.e. we can have a different
circuit for every input length.
```

What I don't understand is why (4) implies that UHALT \in P/Poly.

Thanks!

notin P. $\endgroup$ – Emil Jeřábek supports Monica Mar 3 '11 at 11:25