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.]

what's the most outrageous pair of complexity classes $(C,D)$ such that $C$ is tiny, $D$ is huge, but we don't even know that $C \subsetneq D$?I think that, if we were to play this game on mathoverflow, it would only be of general interest if we all agree tocarefully definethe pairs of classes we give in our answers. O'Donnell is pretty good at this game (he's usually around here) and some others I know are almosttoogood... $\endgroup$ – Ryan Williams Aug 13 '10 at 4:51