摘要：Let ACC◦THR be the class of constant-depth circuits comprised of AND, OR,
and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary
linear threshold functions. This class of circuits can be seen as a “midpoint” between ACC
(where we know nontrivial lower bounds) and depth-two linear threshold circuits (where
nontrivial lower bounds remain open). We give an algorithm for evaluating an arbitrary
symmetric function of 2
n
o(1)
ACC ◦ THR circuits of size 2
n
o(1)
, on all possible inputs, in
2
n
· poly(n) time. Several consequences are derived:
• The number of satisfying assignments to an ACC◦THR circuit of 2
n
o(1)
size is computable
in 2n−n
ε
time (where ε > 0 depends on the depth and modulus of the circuit).
• NEXP does not have quasi-polynomial size ACC◦THR circuits, and NEXP does not
have quasi-polynomial size ACC◦ SYM circuits. Nontrivial size lower bounds were
not known even for AND◦OR◦THR circuits.
• Every 0-1 integer linear program with n Boolean variables and s linear constraints
is solvable in 2
n−Ω(n/log4
(sM(logn)))
· poly(s,n,M) time with high probability, where
M ≤ 2
n
o(1)
is an upper bound on the bit-length of the coefficients. (For example, 0-1
integer programs with weights in [−2
n
o(1)
,2
n
o(1)
] and poly(n) constraints can be solved
in 2n−Ω(n/log4
n)
time.).
关键词：circuit complexity; satisfiability algorithms; linear threshold functions
