2
$\begingroup$

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!

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Mar 3, 2011 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$ Mar 3, 2011 at 15:23
  • $\begingroup$ @ Emil Jerabek: Got it. I'm convinced you're right. Thanks! $\endgroup$ Mar 3, 2011 at 16:45

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.