The following two statements are really "obviously false", but are still open:
$EXP^{NP} subseteq$ depth-2-$TC^0$
$EXP^{NP} subseteq$ depth-2-$AC^0[6]$
Just as a reminder:
$EXP^{NP}$ is exponential time plus an oracle for NP. It contains $NEXP$ (nondeterministic exponential time), $EXP$, and $NP$.
By "depth-2-$TC^0$" I mean the class of polynomial-size, depth-two circuit families where each gate is an arbitrary threshold function -- i.e., if it has $m$ Boolean inputs $x_1, dots, x_m$, it is defined by reals $a_1, dots, a_n, theta$ and has output 1 iff $sum a_i x_i geq theta$.
By depth-2-$AC^0[6]$ I mean the class of polynomial-size, depth-two circuit families where each gate is a "standard" $MOD_6$ gate: if it has $m$ Boolean inputs $x_1, dots, x_m$, it has output 1 iff $sum x_i neq 0$ mod 6.
Expanding on the second open problem: Given $A subseteq mathbb{Z}_6$, define an $A$-$MOD_6$ gate to be one which outputs 1 iff $sum x_i in A$ mod 6.
The most embarrassing open problem in circuit complexity may be the following: Show that for all possible subsets $A$, the AND function requires superpolynomial-size depth-2 circuits of $A$-$MOD_6$ gates.
[PS: Thanks to Arkadev Chattopadhyay for explaining some of these $MOD_6$ problems to me.]
No comments:
Post a Comment