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.


  • $\begingroup$ In (3), you probably wanted to write that HALT (or UHALT) is clearly not in P. $\endgroup$ – Emil Jeřábek Mar 3 '11 at 11:25
  • $\begingroup$ @Emil Jerabek: Good catch. Typo fixed. Thanks! $\endgroup$ – LowerBounds Mar 3 '11 at 15:15

Fix $n$, we want to construct a circuit $C_n$ deciding UHALT on inputs $w$ of length $n$. Now, either $n\notin\mathrm{HALT}$, in which case $C_n$ is the constant $0$ circuit, or $n\in\mathrm{HALT}$, in which case $C_n$ is

$$C_n(w)=\begin{cases}1&\text{if }w\text{ is a string of 1s,}\\0&\text{otherwise,}\end{cases}$$

which can be clearly implemented by a linear-size circuit.

| cite | improve this answer | |
  • $\begingroup$ When constructing the circuit, how do we know whether n \in HALT or n \not\int HALT? Can we arbitrary choose a circuit without showing how to "calculate" it? $\endgroup$ – LowerBounds Mar 3 '11 at 15:16
  • $\begingroup$ Yes, the whole point of non-uniformity is that we can choose the circuit in any odd way, there does not need to be any procedure to compute it. We only have to make sure that the circuit has polynomial size. $\endgroup$ – Emil Jeřábek Mar 3 '11 at 15:23
  • $\begingroup$ @ Emil Jerabek: Got it. I'm convinced you're right. Thanks! $\endgroup$ – LowerBounds Mar 3 '11 at 16:45

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.