ppoly

$\text{[math]}$ is the class of broken link: blk:def-langs that are decidable by polynomial-sized circuit families. that is, $\text{[math]}$ .
[cite:;taken from @computability_arora_2009 definition 6.5]

a most significant question in complexity theory:

is $\text{[math]}$ ?

let $\text{[math]}$ be a unary language (i.e. $\text{[math]}$ ). then, $\text{[math]}$ .
[cite:;taken from @computability_arora_2009 claim 6.8]

we describe a circuit family of linear size. if $\text{[math]}$ , then the circuit for inputs of size $\text{[math]}$ is the circuit from boolean_circuit.html, and otherwise it is the circuit that always outputs 0.
[cite:;taken from @computability_arora_2009 claim 6.8]

one unary language that is undecidable (and yet in $\text{[math]}$ ) is the unary version of the halting problem:
$\text{[math]}$ this language can be solved by the following circuit family construction: for an input of size $\text{[math]}$ place one output gate with the constant 1 iff $\text{[math]}$ some pair $\text{[math]}$ (defined above), and with the constant 0 otherwise, this is possible because no restrictions are imposed on the construction process.
[cite:;found in @computability_arora_2009 chapter 6 boolean circuits]

$\text{[math]}$ .
[cite:;taken from @computability_arora_2009 theorem 6.6]

the proof for the ltr direction is that there are unary languages that are undecidable and hence are not in $\text{[math]}$ (or for that matter in $\text{[math]}$ ), whereas every unary language is in $\text{[math]}$ .

if $\text{[math]}$ then $\text{[math]}$ .

$\text{[math]}$ BROKEN

if $\text{[math]}$ , then $\text{[math]}$ and so $\text{[math]}$ collapses to $\text{[math]}$ .