# Most 'obvious' open problems in complexity theory

What open problems in computational complexity theory have the most 'obvious' answers, regardless of whether that answer is true or false? The problems I'm talking about certainly have more 'obvious' answers than P =?= NP.

I'll start this with

ZPP =?= EXPTIME

• I cannot understand (or even parse) the first sentence. Are you asking to list open problems for which there are generally agreed upon conjectural answers? (Problem being open precludes us from knowing whether an "answer" is right or wrong.) What do the words "most" and "obvious" signify? Aug 13 '10 at 2:48
• That P vs. PSPACE is open always blows my mind. Aug 13 '10 at 4:38
• I think the question is referring to a specific game that bummed-out complexity theorists like to play: 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 to carefully define the 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 almost too good... Aug 13 '10 at 4:51
• Complexity Zoo is a good place to look for such pairs. I think it would be more interesting if you allow things like "pseudo-random number generators exist", and results that say either $\varphi$ or $\psi$ but we don't know which one. Aug 13 '10 at 6:43
• IMHO, the title can be improved. E.g. "Which conjectures are widely believed in complexity theory?" Aug 13 '10 at 6:56

In 1990, my intuition (and I don't think it was just mine) was that IP couldn't possibly contain PSPACE. Intuition was wrong.

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

• Are these also open with DLOGTIME uniformity? Since the specific depth matters, do you label a gate as also the sink, or do you have a special sink vertex?
– user5810
Aug 13 '10 at 19:18
• I just realized, these could be refuted even with NP-uniformity, although it might still be open with coRP-uniformity. I still don't know the answer to my depth question, though.
– user5810
Aug 15 '10 at 18:50
• @Ricky: Not sure what you are referring to. There is a special output gate, is that what you mean by "sink vertex"? Aug 22 '10 at 22:39
– user5810
Sep 9 '10 at 17:40
• @RyanO'Donnell : $\:$ This paper was published almost 2 years after you answered (by the other person who commented on this answer, which I almost didn't notice) and resolves your second example. $\;\;\;\;$
– user5810
Jan 10 '14 at 2:14

$AC^0[6] vs. NP$

In other words, it is open whether $SAT$ has polynomial size constant depth circuits using gates $\land$, $\lor$, $\lnot$, $mod_6$.

I think it is more than obvious, it is kind of embarrassing that we can't prove they are not equal. Note that we know $AC^0[p]$ cannot compute $mod_q$ for $p\neq q \in Primes$. I think the fact that we can't prove a similar result for $mod_6$ is just lack of tools, the tools we have break as soon as we have two $mod$ gates.

## Edit

Note that the barrier results does not seem to apply here.

Uniformity condition: language of direct connection graphs is in $DLogTime$.

• What's the uniformity condition for the circuits? (DLOGTIME, LOGSPACE, none, or something else?)
– user5810
Aug 13 '10 at 6:57
• Dear András Salamon, I rolled back because I meant $AC^0[6]$. $ACC$ is the union of $AC^0[p]$s, I don't know what is $ACC^0[6]$. Aug 13 '10 at 22:55
• According to the references I have on hand, (Complexity Zoo, Arora/Barak, and Immerman's Descriptive Complexity), AC^0 explicitly only allows the usual Boolean operations. ACC^0 allows additional modulo operations, and ACC^0[6] is the class of constant depth circuits with a modulo-6 operation added to the mix. Do you have a reference for your notation? Aug 14 '10 at 15:13
• $AC^0$ is exactly what you say. When we also allow a modm gate we add $(m)$ or $[m]$. Here is one reference: S.A. Cook and P.T. Neguyen "LOGICAL FOUNDATIONS OF PROOF COMPLEXITY", 2010. You can find a draft version of this book here: cs.toronto.edu/~sacook/homepage/book. Note that Ryan is also using the same notation above. Aug 14 '10 at 16:20
• Here is the link to Complexity Zoo page: qwiki.stanford.edu/wiki/Complexity_Zoo:A It defines $AC^0[m]$ as $AC^0$ with $mod_m$ gates, $ACC^0$ is defined as union of $AC^0[p]$s and there is no definition for $ACC^0[m]$. Aug 14 '10 at 16:25

$BQP\subseteq ?PH$

We know that simulating quantum mechanics requires polynomial space, but still is open if wether there are problems that only quantum computers can solve efficiently.

• Forrelation (correlation of Fourier transforms) splits them in a relativized world: quanta article and shtetl-optimized Apr 21 '19 at 22:38

Is integer factorization outside of P?

• How do you state this as a decision problem? Aug 13 '10 at 20:27
• I didn't know this either but found it here: en.wikipedia.org/wiki/Integer_factorization "given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M?" Aug 13 '10 at 21:35
• I have to say that this isn't clear either way. Aug 13 '10 at 23:53

GI $\in$ P. We know that there are bad consequences if GI is NP-complete,

p.s GI is graph isomorphism

• Your pithy statement seems to imply that the only two options are GI being in P or being NP-complete; did you really mean that? If P ≠ NP, then GI could be in one of the infinitely many classes of intermediate complexity between P and NP-complete. Aug 16 '10 at 20:08
• that's definitely true. I guess my belief is that GI is in P. Aug 16 '10 at 21:29

A) Multiplication (of $n$--bit numbers) obviously takes longer than addition.

B) Sorting $n$ objects obviously takes longer than linear time. (I suppose that this is obvious because it is true: there is a lower bound of $n \log n$ for comparison-based sorts. However, radix sort of integers can be faster. In fact, for any collection (of a particular type of object), there just might be a super clever way to sort it faster than $n \log n$....)