14
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ 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? $\endgroup$
    – Victor Protsak
    Commented Aug 13, 2010 at 2:48
  • 7
    $\begingroup$ That P vs. PSPACE is open always blows my mind. $\endgroup$
    – Noah Snyder
    Commented Aug 13, 2010 at 4:38
  • 10
    $\begingroup$ 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... $\endgroup$
    – Ryan Williams
    Commented Aug 13, 2010 at 4:51
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Aug 13, 2010 at 6:43
  • 3
    $\begingroup$ IMHO, the title can be improved. E.g. "Which conjectures are widely believed in complexity theory?" $\endgroup$
    – Kaveh
    Commented Aug 13, 2010 at 6:56

7 Answers 7

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – user5810
    Commented Aug 13, 2010 at 19:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – user5810
    Commented Aug 15, 2010 at 18:50
  • $\begingroup$ @Ricky: Not sure what you are referring to. There is a special output gate, is that what you mean by "sink vertex"? $\endgroup$
    – Ryan Williams
    Commented Aug 22, 2010 at 22:39
  • $\begingroup$ (You've probably forgotten about this question by now, but) Yes. $\endgroup$
    – user5810
    Commented Sep 9, 2010 at 17:40
  • 2
    $\begingroup$ @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. $\;\;\;\;$ $\endgroup$
    – user5810
    Commented Jan 10, 2014 at 2:14
3
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ What's the uniformity condition for the circuits? (DLOGTIME, LOGSPACE, none, or something else?) $\endgroup$
    – user5810
    Commented Aug 13, 2010 at 6:57
  • $\begingroup$ 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]$. $\endgroup$
    – Kaveh
    Commented Aug 13, 2010 at 22:55
  • 1
    $\begingroup$ 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? $\endgroup$
    – András Salamon
    Commented Aug 14, 2010 at 15:13
  • $\begingroup$ $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. $\endgroup$
    – Kaveh
    Commented Aug 14, 2010 at 16:20
  • $\begingroup$ 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]$. $\endgroup$
    – Kaveh
    Commented Aug 14, 2010 at 16:25
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Forrelation (correlation of Fourier transforms) splits them in a relativized world: quanta article and shtetl-optimized $\endgroup$
    – Mark S
    Commented Apr 21, 2019 at 22:38
2
$\begingroup$

Is integer factorization outside of P?

Improve this answer
$\endgroup$
3
  • $\begingroup$ How do you state this as a decision problem? $\endgroup$
    – Andrés E. Caicedo
    Commented Aug 13, 2010 at 20:27
  • $\begingroup$ 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?" $\endgroup$
    – Dan Brumleve
    Commented Aug 13, 2010 at 21:35
  • 10
    $\begingroup$ I have to say that this isn't clear either way. $\endgroup$
    – Peter Shor
    Commented Aug 13, 2010 at 23:53
2
$\begingroup$

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

p.s GI is graph isomorphism

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Aug 16, 2010 at 20:08
  • $\begingroup$ that's definitely true. I guess my belief is that GI is in P. $\endgroup$
    – Suresh Venkat
    Commented Aug 16, 2010 at 21:29
2
$\begingroup$

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$....)

Improve this answer
$\endgroup$

You must log in to answer this question.