32
$\begingroup$

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves.

To be more precise, let's say a problem has gap classes $A,B$ (with $A\subseteq B$, not uniquely defined) if $A$ is a maximal class for which we can prove it is $A$-hard, and $B$ is a minimal known upper bound, i.e. we have an algorithm in $B$ solving the problem. This means if we end up finding out that the problem is $C$-complete with $A\subseteq C\subseteq B$, it will not impact complexity theory in general, as opposed to finding a $P$ algorithm for a $NP$-complete problem.

I am not interested in problems with $A\subseteq P$ and $B=NP$, because it is already the object of this question.

I am looking for examples of problems with gap classes that are as far as possible. To limit the scope and precise the question, I am especially interested in problems with $A\subseteq P$ and $B\supseteq EXPTIME$, meaning both membership in $P$ and $EXPTIME$-completeness are coherent with current knowledge, without making known classes collapse (say classes from this list).

$\endgroup$
  • $\begingroup$ What do you mean by classes of a problem? Assume the problem is SAT, how do you define classes? $\endgroup$ – R B Feb 26 '15 at 12:20
  • $\begingroup$ SAT is NP-complete so we can take $A=B=NP$ and there is no gap here, because the complexity of SAT matches exactly an already well-known class. Showing any new result on the complexity of SAT (namely belonging to a smaller class) would be a breakthrough in complexity theory. Granted the question is not completely well-defined, as it depends on which complexity classes are considered "mainstream", and $A,B$ are not uniquely defined. The specific question though is well-defined: examples of languages for which it is coherent with current knowledge that they are in P or EXPTIME-complete. $\endgroup$ – Denis Feb 26 '15 at 12:26
  • $\begingroup$ actually still not completely well-defined because of the "non-collapsing", so it relies on a notion of "well-known class". Obviously a PSPACE-complete problem does not fit the requirement, although being in P or EXPTIME-complete is coherent with current knowledge. For instance this list can be used as reference for what is a "well-known" class: en.wikipedia.org/wiki/List_of_complexity_classes $\endgroup$ – Denis Feb 26 '15 at 12:54
  • 13
    $\begingroup$ It doesn't quite fit the bill of your specific question but to all appearances the existential theory of the reals stubbornly resists any further classification beyond being NP-hard and within PSPACE (the latter per 1988 result of J.F. Canny). en.wikipedia.org/wiki/Existential_theory_of_the_reals $\endgroup$ – anemone Feb 26 '15 at 22:19
28
$\begingroup$

The Knot Equivalence Problem.

Given two knots drawn in the plane, are they topologically the same? This problem is known to be decidable, and there do not seem to be any computational complexity obstructions to its being in P. The best upper bound currently known on its time complexity seems to be a tower of $2$s of height $c^n$, where $c = 10^{10^{6}}$, and $n$ is the number of crossings in the knot diagrams. This comes from a bound by Coward and Lackenby on the number of Reidemeister moves needed to take one knot to an equivalent one. See Lackenby's more recent paper for some more recent related results and for the explicit form of the bound I give above (page 16).

$\endgroup$
  • $\begingroup$ Thank you for your answer. Do you know the current bounds? Can you point to a reference stating the current state of the art? I am having trouble finding a clear one. $\endgroup$ – Denis Feb 26 '15 at 14:30
  • $\begingroup$ I've been trying go find something more recent than the 1998 paper of Hass, Lagarias, and Pippenger here. This states that the knot equivalence problem is known to be decidable. I wouldn't be surprised if somebody had shown that it was in EXPTIME since then, but I don't believe anything better than that is known, and it certainly isn't clear that it's not in P. I am fairly sure that none of the results showing that deciding whether something is knotted is in NP extend to this more general problem. $\endgroup$ – Peter Shor Feb 26 '15 at 15:39
  • $\begingroup$ This MO question is related: mathoverflow.net/questions/77786/… In particular, using recent results announced by Lackenby in people.maths.ox.ac.uk/lackenby/ekt11214.pdf , one obtains that for any knot type K, determining if a given knot is equivalent to K is in NP (note that this does not improve on the Knot Equivalence Problem) $\endgroup$ – Arnaud Feb 27 '15 at 15:42
  • $\begingroup$ @Arnaud: in fact, it looks to me like these results prove that for two diagrams with at most n crossings, the Knot Equivalence Problem can be solved in time at most a tower of 2's of height $c^n$, where $c$ is an enormous constant. I should check this and edit my answer. $\endgroup$ – Peter Shor Feb 27 '15 at 15:58
  • $\begingroup$ @PeterShor Yes indeed. I was focusing on the more recent result because it may lead to an improved bound when it is published, if the actual polynomial is explicited. $\endgroup$ – Arnaud Feb 27 '15 at 16:42
23
$\begingroup$

Here's a version of the minimum circuit size problem (MCSP): given the $2^n$ bit truth table of a Boolean function, does it have a circuit of size at most $2^{n/2}$?

Known to be not in $AC0$. Contained in $NP$. Generally believed to be $NP$-hard, but this is open. I believe it's not even known to be $AC0[2]$-hard. Indeed, recent work with Cody Murray (to appear in CCC'15) shows there's no uniform NC0 reduction from PARITY to MCSP.

$\endgroup$
23
$\begingroup$

The complexity of computing a bit (specified in binary) of an irrational algebraic number (such as $\sqrt{2}$) has the best known upper bound of $\mathsf{P^{{{PP}^{PP}}^{PP}}}$ via a reduction to the problem $\mathsf{BitSLP}$ which known to have this upper bound [ABD14]. On the other hand we do not even know if this problem is harder than computing the parity of $n$ bits - for all we know this problem could be in $\mathsf{AC^0}$. Notice however that we know that no finite automaton can compute the bits of an irrational algebraic number [AB07]

$\endgroup$
21
$\begingroup$

Another natural topological problem, similar in spirit to Peter Shor's answer, is embeddability of 2-dimensional abstract simplicial complexes in $\mathbb{R}^3$. In general it's natural to ask when can we effectively/efficiently decide that an abstract $k$-dimensional simplicial complex can be embedded in $\mathbb{R}^d$. For $k=1$ and $d=2$ this is the graph planarity problem and has a linear-time algorithm. For $k=2$ and $d=2$ there is also a linear time algorithm. The $k=2$, $d=3$ case was open until last year, when it was shown to be decidable by Matousek, Sedgwick, Tancer, and Wagner. They say that their algorithm has a primitive recursive time bound, but larger than a tower of exponentials. On the other hand they speculate that it might be possible to put the problem in NP, but going beyond that would be challenging. However, there doesn't seem to be any strong evidence that a polytime algorithm is impossible.

The latter paper has many references for further reading.

$\endgroup$
16
$\begingroup$

Multicounter automata (MCAs) are finite automata equipped with counters that can be incremented and decremented within one step but only take integers >=0 as numbers. Unlike Minsky machines (aka counter automata), MCAs are not allowed to test whether a counter is zero.

One of the algorithmic problems with a huge gap related to MSCs is the Reachability problem. E.g., whether the automaton can reach, from a configuration with the initial state and all counters zero, a configuration with an accepting state, and all counters zero again.

The problem is hard for EXPTIME (as shown by Richard Lipton in 1976), decidable (Ernst Mayr, 1981) and solvable in Fω3 (thanks, Sylvain, for pointing this out). A huge gap.

$\endgroup$
  • 3
    $\begingroup$ Hi Thomas, there is a claim of an explicit (and most likely not tight) complexity upper bound in a recent arXiv paper: arxiv.org/abs/1503.00745. The proposed upper bound in $\mathbf{F}_{\omega^3}$ is however way beyond the complexity classes the original poster was interested in. $\endgroup$ – Sylvain Mar 5 '15 at 13:42
  • $\begingroup$ @Sylvain Cool! Thanks for sharing this. :) $\endgroup$ – Michael Wehar Mar 6 '15 at 0:11
  • $\begingroup$ @Sylvain Is EXPTIME the best known lower bound? $\endgroup$ – Michael Wehar Mar 6 '15 at 0:13
  • 2
    $\begingroup$ @Michael: the best lower bound on the decision problem is actually EXPSPACE (Lipton, 1976, cpsc.yale.edu/sites/default/files/files/tr63.pdf). However, the algorithm by Mayr (1981, dx.doi.org/10.1145/800076.802477), Kosaraju (1982, dx.doi.org/10.1145/800070.802201), and Lambert (1992, dx.doi.org/10.1016/0304-3975(92)90173-D) analysed in the mentioned arXiv paper is known to require at least Ackermannian (i.e., $\mathbf{F}_\omega$) time. $\endgroup$ – Sylvain Mar 6 '15 at 9:57
  • $\begingroup$ @Sylvain Thank you very much for all of the additional information. I really appreciate it. :) $\endgroup$ – Michael Wehar Mar 6 '15 at 23:44
11
$\begingroup$

$\mathsf{QMA}(2)$ (Quantum Merlin-Arthur with two unentangled provers): certainly $\mathsf{QMA}$-hard, but only known to be in $\mathsf{NEXP}$.

$\endgroup$
9
$\begingroup$

The computational problem associated to Noether's Normalization Lemma for explicit varieties ("explicit" in the sense of this paper [freely available full version]). Best known upper bound is $\mathsf{EXPSPACE}$ (note, SPACE, not TIME!) but it is conjectured to be in $\mathsf{P}$ (and indeed, its being in $\mathsf{P}$ is essentially equivalent to derandomizing PIT).

$\endgroup$
  • $\begingroup$ Can you provide more info on this in an explicit form? looks like some kind of bpp-complete problem? $\endgroup$ – user34945 Oct 17 '15 at 19:32
  • $\begingroup$ @Arul: Neither PIT nor this problem is BPP-complete in any sense that I am aware of. (In fact, showing that BPP-complete problems exist is still open, and requires non-relativizing techniques - a result going back to Sipser.) However, derandomizing either has a hardness-randomness trade-off, in that their derandomization is essentially equivalent to lower bounds. Aside from the paper linked in the answer ("GCT 5"), lookup hardness-randomness and Kabanets-Impagliazzo. $\endgroup$ – Joshua Grochow Oct 18 '15 at 17:16
  • $\begingroup$ I will do that but I was interested in this phrase 'and indeed, its being in P is essentially equivalent to derandomizing PIT' which seems to say PIT is some kind of proxy complete problem $\endgroup$ – user34945 Oct 18 '15 at 17:56
  • $\begingroup$ @Arul: Yes, to see why PIT is such a "proxy complete problem," see the things I referred to in my previous comment. $\endgroup$ – Joshua Grochow Oct 18 '15 at 17:58
  • $\begingroup$ why does he use 'Dedicated to Sri Ramakrishna' in many of his works? $\endgroup$ – user34945 Oct 18 '15 at 18:12
6
$\begingroup$

The Skolem problem (given a linear recurrence with integer base cases and integer coefficients, does it ever reach the value 0) is known to be NP-hard and not known to be decidable. As far as I know anything in between would be consistent with our current knowledge without any collapses of standard complexity classes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.