AC class

<2024-12-30 Mon 20:56:31> mahmood
cs
the "A" in AC stands for "alternating", in reference to alternating turing machines.
for , define
and let
[cite:;taken from @complexity_vollmer_1999 definition 4.5]
a connection to the classes of the NC hierarchy can be stated as follows:
for all , we have ; hence .
the following is an open question:
is there a function in that every circuit in with depth 3 that computes it has to be of size atleast ? or even for some .
an circuit is a standard circuit iff:
  1. the circuit is divided into layers, such that edges only connect vertices between subsequent layers.
  2. in each layer there are only or gates (except the input layer).
  3. in subsequent layers there are only different types of gates (e.g. an AND layer is followed by an OR layer, and vice versa).
we say the circuit is very standard if the indegree of each gate in the first (non-input) layer is at most , where is the size of the circuit.
every circuit can be turned into a standard AC circuit such that if the original circuit is of size and depth then the new circuit would be of depth and at most of size .
note that two consecutive gates are redundant if you are allowed to have arbitrary fan-in. the same applies to gates.
let be a function that can be computed by a standard circuit of size and depth , and let be a -random restriction. then with probability of atleast we can compute using a very standard circuit of size at most and depth (i.e. to every gate in the first non-input layer we have an indegree of at most ).
let be the circuit that computes , we prove that with a probability of atleast all gates in the first layer of with more than than ingoing edges, turn into constants as a consequence of the assignment . the circuit that remains would be a very standard circuit that computes . let be a gate with ingoing edges for in the first layer. assume that is an OR gate, then isnt set to 1 iff didnt set any of the literals going into to 1. is the probability for a literal to not be set to 1, meaning either it gets set to 0 or it stays alive, hence the case where none of the edges get set to 1 happens with a probability of at most
we get that the probability that a single gate isnt set to a constant is at most , and there are at most such gates, hence the probability that atleast one of them isnt set to a constant is at most (we know that for every events we have ). it follows that with a probability of atleast all of them are set to constants.
a very standard circuit of depth that computes has to be of size atleast .
AC circuits by definition have polynomial size, what we mean here is that no AC circuit of polynomial size can compute parity, as we would to extend the class AC to allow for exponential size circuits.
[cite:;variant of @complexity_jukna_2012 theorem 12.3]
let such that , if there exists a very standard AC circuit of depth and size that computes or then there exists some very standard AC circuit of depth and size at most that computes or .
let , let be a standard AC circuit that computes , notice that the gates in the second layer of the circuit compute -cnf and -dnf formulas. without loss of generality we assume -cnf. let be a random restriction that keeps alive variables (). by the switching lemma, after the assignment we can replace every gate of the second layer with a -dnf with a probability of atleast . there is at most vertices in the sescond layer, therefore the probability that one of them isnt replaceable by a -dnf after the assignment is at most
hence there exists some assignment that if we apply we can turn all of the gates in the second layer into -dnf, and keep alive variables. after this assignment, the circuit computes or , and both the second and third layer compute OR gates. notice that since an OR of OR's is an OR, we can merge those layers and receive a standard layer of depth .
assume that such a circuit exists of depth and size . if the claim is true by clm-bool-formula-2 because standard AC circuits of depth 2 are simply DNF or CNF formulas. if , we apply ac_class.html times, and get a circuit of depth 2 and size at most that computes or . the size of such a circuit is atleast , meaning meaning and so
( circuits with constant depth) cannot compute .
since cannot compute parity, one can try to empower it by allowing new gates:
is the circuit class in which a circuit is under the restriction of , but allowed to use parity gates.
however, we can show that this circuit class is still not powerful enough to compute all functions. which is why we try to generalize it again with the following class.
is the circuit class in which a circuit is under the restriction of , but allowed to use gates where .
BROKEN
and the new task becomes to bound the complexity of functions that can feasibly compute. a more formal definition for is given below:
for .
[cite:;taken from @complexity_vollmer_1999 definition 4.34]