<p>The <strong>Knot Equivalence Problem</strong>. </p>

<p>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 <a href="http://arxiv.org/abs/1104.1882">Coward and Lackenby</a> on the number of Reidemeister moves needed to take one knot to an equivalent one. See <a href="http://people.maths.ox.ac.uk/lackenby/ekt11214.pdf">Lackenby's more recent paper</a> for some more recent related results and for 
the explicit form of the bound I give above (page 16). </p>

CC BY-SA 3.0
2015-02-26T14:30:53.097Z
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.
Denis
CC BY-SA 3.0
2015-02-26T15:39:28.390Z
I've been trying go find something more recent than the 1998 paper of Hass, Lagarias, and Pippenger [here](http://arxiv.org/abs/math/9807016). 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.
Peter Shor 
CC BY-SA 3.0
2015-02-27T15:42:19.533Z
This MO question is related: http://mathoverflow.net/questions/77786/number-of-the-reidemeister-moves-needed-to-transform-one-diagram-into-another-on

In particular, using recent results announced by Lackenby in 
http://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)
Arnaud
CC BY-SA 3.0
2015-02-27T15:58:43.010Z
@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.
Peter Shor 
CC BY-SA 3.0
2015-02-27T16:42:49.897Z
@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.
Arnaud
CC BY-SA 3.0
2015-02-26T13:26:35.797Z
2015-02-27T21:06:32.743Z
2015-02-27T21:06:32.743Z
Peter Shor 
<p>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 <a href="http://ftp.cs.rutgers.edu/pub/allender/slp.pdf">$\mathsf{BitSLP}$</a> which known to have this upper bound <a href="http://link.springer.com/chapter/10.1007%2F978-3-662-44465-8_2">[ABD14]</a>. 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 <a href="http://www-irma.u-strasbg.fr/~bugeaud/travaux/AdBuAnn1.pdf">[AB07]</a></p>

CC BY-SA 3.0
2015-02-27T14:05:49.007Z
2015-02-28T18:05:38.703Z
2015-02-28T18:05:38.703Z
SamiD
<p>Another natural topological problem, similar in spirit to Peter Shor's answer, is <strong>embeddability of 2-dimensional abstract simplicial complexes in $\mathbb{R}^3$</strong>. In general it's natural to ask when can we effectively/efficiently decide that an <a href="http://en.wikipedia.org/wiki/Abstract_simplicial_complex">abstract $k$-dimensional simplicial complex</a> can be embedded in $\mathbb{R}^d$. For $k=1$ and $d=2$ this is the <em>graph planarity</em> problem and has a linear-time algorithm. For $k=2$ and $d=2$ there is also a <a href="http://dl.acm.org/citation.cfm?id=322156">linear time algorithm</a>. The $k=2$, $d=3$ case was open until last year, when it was <a href="http://arxiv.org/abs/1402.0815">shown to be decidable by Matousek, Sedgwick, Tancer, and Wagner</a>. They say that their algorithm has a <em>primitive recursive</em> time bound, but <em>larger than a tower of exponentials</em>. 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.</p>

<p>The latter paper has many references for further reading.</p>

CC BY-SA 3.0
2015-02-26T19:19:14.117Z
2015-02-27T21:53:30.443Z
2015-02-27T21:53:30.443Z
Sasho Nikolov
<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-05T13:42:59.800Z
Hi Thomas, there is a claim of an explicit (and most likely not tight) complexity upper bound in a recent arXiv paper: http://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.
Sylvain
CC BY-SA 3.0
2015-03-06T00:11:10.353Z
@Sylvain Cool!  Thanks for sharing this.  :)
Michael Wehar
CC BY-SA 3.0
2015-03-06T00:13:06.833Z
@Sylvain Is EXPTIME the best known lower bound?
Michael Wehar
CC BY-SA 3.0
2015-03-06T09:57:31.760Z
@Michael: the best lower bound on the decision problem is actually EXPSPACE (Lipton, 1976, http://cpsc.yale.edu/sites/default/files/files/tr63.pdf).  However, the algorithm by Mayr (1981, http://dx.doi.org/10.1145/800076.802477), Kosaraju (1982, http://dx.doi.org/10.1145/800070.802201), and Lambert (1992, http://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.
Sylvain
CC BY-SA 3.0
2015-03-06T23:44:06.083Z
@Sylvain Thank you very much for all of the additional information.  I really appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2015-02-27T21:38:43.650Z
2015-03-05T17:59:43.193Z
2015-03-05T17:59:43.193Z
Thomas S
<p>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}$?</p>

<p>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 <em>no</em> uniform NC0 reduction from PARITY to MCSP.</p>

CC BY-SA 4.0
2021-03-21T06:47:09.557Z
So Parity here is given a $0/1$ string of length $2^n$ what is the parity?
Turbo
CC BY-SA 3.0
2015-02-27T02:23:28.953Z
2015-02-27T02:23:28.953Z
Ryan Williams
<p>$\mathsf{QMA}(2)$ (Quantum Merlin-Arthur with two unentangled provers): certainly $\mathsf{QMA}$-hard, but only known to be in $\mathsf{NEXP}$.  </p>

CC BY-SA 3.0
2015-02-27T12:35:26.670Z
2015-10-15T06:10:35.890Z
2015-10-15T06:10:35.890Z
Martin Schwarz
<p>The <a href="https://en.wikipedia.org/wiki/Skolem_problem">Skolem problem</a> (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.</p>

CC BY-SA 3.0
2015-10-17T04:48:47.200Z
2015-10-17T04:48:47.200Z
David Eppstein
<p>The computational problem associated to Noether's Normalization Lemma for explicit varieties ("explicit" in the sense of <a href="http://ieee-focs.org/FOCS-2012-Papers/4874a629.pdf">this paper</a> [<a href="http://gct.cs.uchicago.edu/gct5.pdf">freely available full version</a>]). 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).</p>

CC BY-SA 3.0
2015-10-18T17:16:29.980Z
@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.
Joshua Grochow
CC BY-SA 3.0
2015-10-18T17:58:24.543Z
@Arul: Yes, to see why PIT is such a "proxy complete problem," see the things I referred to in my previous comment.
Joshua Grochow
CC BY-SA 3.0
2015-03-09T04:35:35.880Z
2015-03-09T04:35:35.880Z
Joshua Grochow
<p>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.</p>

<p>To be more precise, let's say a problem has <em>gap classes</em> $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.</p>

<p>I am not interested in problems with $A\subseteq P$ and $B=NP$, because it is already the object of <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">this question</a>.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/List_of_complexity_classes" rel="noreferrer">this list</a>). </p>

CC BY-SA 3.0
2015-02-26T12:20:31.017Z
What do you mean by classes of a problem? Assume the problem is SAT, how do you define classes?
R B
CC BY-SA 3.0
2015-02-26T12:26:53.707Z
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.
Denis
CC BY-SA 3.0
2015-02-26T12:54:37.857Z
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: http://en.wikipedia.org/wiki/List_of_complexity_classes
Denis
CC BY-SA 3.0
2015-02-26T22:19:09.977Z
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). http://en.wikipedia.org/wiki/Existential_theory_of_the_reals
anemone
<cc.complexity-theory><complexity-classes><big-list>
Problems with big open complexity gaps
Denis
# Problems with big open complexity gaps

(Asked by: username_0 on 2015-02-26)

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](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc).

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](http://en.wikipedia.org/wiki/List_of_complexity_classes)).

**Tags:** cc.complexity-theory, complexity-classes, big-list
> **Comments:**
> **username_1**: What do you mean by classes of a problem? Assume the problem is SAT, how do you define classes?  
> **username_0**: 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.  
> **username_0**: 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: http://en.wikipedia.org/wiki/List_of_complexity_classes  
> **username_2**: 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). http://en.wikipedia.org/wiki/Existential_theory_of_the_reals  

---

## 8 answers

### Answer by username_3 on 2015-02-26. Score: 30

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](http://arxiv.org/abs/1104.1882) on the number of Reidemeister moves needed to take one knot to an equivalent one. See [Lackenby's more recent paper](http://people.maths.ox.ac.uk/lackenby/ekt11214.pdf) for some more recent related results and for
the explicit form of the bound I give above (page 16).

> **Comments:**
> **username_0**: 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.  
> **username_3**: I've been trying go find something more recent than the 1998 paper of Hass, Lagarias, and Pippenger [here](http://arxiv.org/abs/math/9807016). 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.  
> **username_4**: This MO question is related: http://mathoverflow.net/questions/77786/number-of-the-reidemeister-moves-needed-to-transform-one-diagram-into-another-on  In particular, using recent results announced by Lackenby in  http://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)  
> **username_3**: @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.  
> **username_4**: @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.  

---

### Answer by username_5 on 2015-02-27. Score: 24

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}$](http://ftp.cs.rutgers.edu/pub/allender/slp.pdf) which known to have this upper bound [[ABD14]](http://link.springer.com/chapter/10.1007%2F978-3-662-44465-8_2). 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]](http://www-irma.u-strasbg.fr/~bugeaud/travaux/AdBuAnn1.pdf)


---

### Answer by username_10 on 2015-02-27. Score: 24

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.

> **Comments:**
> **username_11**: So Parity here is given a $0/1$ string of length $2^n$ what is the parity?  

---

### Answer by username_6 on 2015-02-26. Score: 22

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](http://en.wikipedia.org/wiki/Abstract_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](http://dl.acm.org/citation.cfm?id=322156). The $k=2$, $d=3$ case was open until last year, when it was [shown to be decidable by Matousek, Sedgwick, Tancer, and Wagner](http://arxiv.org/abs/1402.0815). 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.


---

### Answer by username_7 on 2015-02-27. Score: 17

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.

> **Comments:**
> **username_8**: Hi Thomas, there is a claim of an explicit (and most likely not tight) complexity upper bound in a recent arXiv paper: http://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.  
> **username_9**: @Sylvain Cool!  Thanks for sharing this.  :)  
> **username_9**: @Sylvain Is EXPTIME the best known lower bound?  
> **username_8**: @Michael: the best lower bound on the decision problem is actually EXPSPACE (Lipton, 1976, http://cpsc.yale.edu/sites/default/files/files/tr63.pdf).  However, the algorithm by Mayr (1981, http://dx.doi.org/10.1145/800076.802477), Kosaraju (1982, http://dx.doi.org/10.1145/800070.802201), and Lambert (1992, http://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.  
> **username_9**: @Sylvain Thank you very much for all of the additional information.  I really appreciate it.  :)  

---

### Answer by username_12 on 2015-02-27. Score: 12

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


---

### Answer by username_13 on 2015-10-17. Score: 11

The [Skolem problem](https://en.wikipedia.org/wiki/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.


---

### Answer by username_14 on 2015-03-09. Score: 10

The computational problem associated to Noether's Normalization Lemma for explicit varieties ("explicit" in the sense of [this paper](http://ieee-focs.org/FOCS-2012-Papers/4874a629.pdf) [[freely available full version](http://gct.cs.uchicago.edu/gct5.pdf)]). 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).

> **Comments:**
> **username_14**: @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.  
> **username_14**: @Arul: Yes, to see why PIT is such a "proxy complete problem," see the things I referred to in my previous comment.  

---

