<p>Adding a few more with emphasis on Galois theory and computational Galois theory (see <a href="https://cs.stackexchange.com/a/41740/17369">related question on cs.SE</a>):</p>

<p>The computational complexity of determining if a given monic irreducible polynomial over the integers $\mathbb{Z}$, is soluble by radicals is in $\mathbb{P}$ Ref <a href="https://www.cs.cmu.edu/~glmiller/Publications/Papers/LaMi85.pdf" rel="nofollow noreferrer">"Solvability by Radicals Is in Polynomial Time", S. Landau G.L Miller 1984</a></p>

<blockquote>
  <p>According to a paper Upper bounds on the complexity of some Galois
  Theory problems by Arvind and Kurur
  <a href="http://www.cse.iitk.ac.in/users/ppk/research/publication/AK2003.pdf" rel="nofollow noreferrer">here</a>,
  a theorem of Landau gives an exponential upper bound in the size of
  the polynomial under a certain definition of size. More precisely, her
  theorem gives a polynomial bound in terms of the size of the Galois
  group and the size of the polynomial. But the size of the group can be
  exponential in the size of the polynomial. They show if the Galois
  group is solvable, then the order can be computed by a randomized
  polynomial time algorithm with an $NP$ oracle.</p>
</blockquote>

<p>reproduced from <a href="https://mathoverflow.net/a/149508/50427">linked question on MO</a></p>

CC BY-SA 3.0
2015-04-27T21:46:50.933Z
2015-04-27T21:46:50.933Z
2017-04-13T12:57:54.777Z
Nikos M.
<p><strong>Algebraic geometry</strong></p>

<ul>
<li><p>Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is <a href="http://gct.cs.uchicago.edu/gct5.pdf" rel="nofollow noreferrer">conjectured</a> to be in $\mathsf{P}$ (and is in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $\mathsf{PSPACE}$ over the rationals (<a href="https://arxiv.org/abs/1712.09967" rel="nofollow noreferrer">Forbes &amp; Shpilka)</a> and then over arbitrary fields (<a href="https://arxiv.org/abs/1801.09275" rel="nofollow noreferrer">Guo, Saxena, &amp; Sinhababu</a>).</p></li>
<li><p>Testing whether a given set of polynomials has an algebraic dependence. This problem was recently shown to be in $\mathsf{AM} \cap \mathsf{coAM}$ by  <a href="https://arxiv.org/abs/1801.09275" rel="nofollow noreferrer">Guo, Saxena, &amp; Sinhababu</a> (improving the previous upper bound of $\mathsf{NP}^{\mathsf{\# P}}$ due to <a href="https://doi.org/10.1090/S0002-9947-2014-06268-5" rel="nofollow noreferrer">Mittmann, Saxena, &amp; Scheblechner</a>, also on the <a href="https://arxiv.org/abs/1202.4301" rel="nofollow noreferrer">arXiv</a>).</p></li>
<li><p>There are <a href="http://link.springer.com/article/10.1007%2Fs10208-012-9123-y" rel="nofollow noreferrer">several</a> (<a href="https://arxiv.org/abs/0905.2212" rel="nofollow noreferrer">arXiv</a>) <a href="http://www.sciencedirect.com/science/article/pii/S0747717109000133" rel="nofollow noreferrer">new</a> algorithms for computing topological invariants of complex varieties (with various restrictions like smoothness, etc.). I believe for most of these the optimal upper bound is still open.</p></li>
<li><p>Hilbert's Nullstellensatz (HN): given integer polynomials, decide if they have a common complex solution, is in $\mathsf{AM}$ assuming GRH (<a href="http://dx.doi.org/10.1006/jcom.1996.0019" rel="nofollow noreferrer">Koiran</a>). It is unknown if it is in $\mathsf{NP}$.</p></li>
<li><p>Algorithms for resolution of singularities of algebraic varieties in characteristic zero. The <a href="http://www.ams.org/mathscinet-getitem?mr=2838220" rel="nofollow noreferrer">current best time upper bound</a>, due to <a href="http://logic.pdmi.ras.ru/~grigorev/pub/hiron-complex_journal.pdf" rel="nofollow noreferrer">Bierstone, Grigoriev, Milman, and Włodarczyk</a> is $\mathcal{E}^{d+3}$ where $d$ is the dimension of the variety and $\mathcal{E}^{\bullet}$ is the <a href="http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy" rel="nofollow noreferrer">Grzegorczyk hierarchy of primitive recursive functions</a>. There aren't particularly good (any?) lower bounds on this problem, but for a seemingly much simpler problems related lower bounds are known, namely: There are ideals in $n$ variables generated in degree at most $n$ that require $\mathcal{E}^{n+1}$ such generators. So the current upper bound for resolution of singularities may not be far from the truth, but little is really known.</p></li>
</ul>

<p><strong>Isomorphism problems</strong></p>

<ul>
<li><p>Many problems on permutation groups - such as coset intersection, permutation group isomorphism, etc. - are in $\mathsf{NP} \cap \mathsf{coAM}$, but it is unknown if they are in $\mathsf{NP} \cap \mathsf{coNP}$, and it is suspected that they are not in $\mathsf{P}$. Graph Isomorphism reduces to most of those problems, so a better upper bound on them implies a better upper bound on GI. </p></li>
<li><p>In particular, for permutation group isomorphism, the <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-31594-7_5" rel="nofollow noreferrer">current best upper bound</a> is $2^{O(n)}|G|$, and it is open if it can be done in $2^{O(n)}$ time (depending only on the degree of the permutation group and not on its order), let alone <a href="https://arxiv.org/abs/1512.03547" rel="nofollow noreferrer">quasi-poly time like GI and coset intersection</a>.</p></li>
<li><p>Group Isomorphism where groups are given by multiplication tables is known to be in $\mathsf{TIME}(n^{O(\log n)})$, but is suspected to be in $\mathsf{P}$. Known to be in $\mathsf{P}$ for <a href="http://arxiv.org/abs/1309.1776" rel="nofollow noreferrer">several</a> <a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2012.453" rel="nofollow noreferrer">classes</a> of <a href="https://arxiv.org/abs/1010.5466" rel="nofollow noreferrer">groups</a> (update 4/18/18: and a <a href="https://doi.org/10.1016/j.jalgebra.2016.12.007" rel="nofollow noreferrer">couple</a> (<a href="https://arxiv.org/abs/1508.03033" rel="nofollow noreferrer">arXiv</a>) <a href="http://dx.doi.org/10.1007/978-3-662-48971-0_49" rel="nofollow noreferrer">more</a> (<a href="http://arxiv.org/abs/1507.01917" rel="nofollow noreferrer">arXiv</a>)), but not in general.</p></li>
</ul>

<p><strong>Other</strong></p>

<ul>
<li><p>Update 4/18/18: Tensor rank over any field $\mathbb{F}$ is $\exists \mathbb{F}$-complete (<a href="https://arxiv.org/abs/1612.04338" rel="nofollow noreferrer">Schaefer &amp; Stefankovic</a>). <s>Is tensor rank over $\mathbb{Q}$ in $\mathsf{NP}$?</s> It is known to be $\mathsf{NP}$-hard (<a href="http://dx.doi.org/10.1016/0196-6774(90)90014-6" rel="nofollow noreferrer">Håstad</a>), and over finite fields it is in $\mathsf{NP}$.</p></li>
<li><p>More generally, many problems on tensors over $\mathbb{Q}$ are $\mathsf{NP}$-hard but not known to be in $\mathsf{NP}$ (<a href="http://dx.doi.org/10.1145/2512329" rel="nofollow noreferrer">Hillar and Lim</a>, also on the <a href="http://arxiv.org/abs/0911.1393" rel="nofollow noreferrer">arXiv</a>).</p></li>
</ul>

<p>It would (somewhat sadly) seem that the Adleman-McCurley survey, despite being 21 years old, is pretty up to date in terms of number-theoretic problems, with the exception of the fact that we now know that <a href="http://dx.doi.org/10.4007%2Fannals.2004.160.781" rel="nofollow noreferrer">$\mathsf{PRIMES}$ is in $\mathsf{P}$</a>...</p>

CC BY-SA 3.0
2015-04-24T19:46:11.590Z
I am surprised HN is in NP is unknown. All you have to do is check solution for each polynomial right?
Turbo
CC BY-SA 3.0
2015-04-24T19:47:10.263Z
IWhat is the gap in resolution of singularities?
Turbo
CC BY-SA 3.0
2015-04-24T19:49:52.060Z
@Turbo: For HN, the polynomials are integer polynomials, but the solutions are allowed to be complex numbers that need not even be expressible by a finite number of bits, let alone a polynomial number of bits. Also, to even get AM I think you need GRH.
Joshua Grochow
CC BY-SA 3.0
2015-04-24T19:59:14.777Z
Ok it is not clear to me, if input is not in finite number of bits, how do you define its complexity?
Turbo
CC BY-SA 3.0
2015-04-24T21:26:27.983Z
(First I confirm the proof that HN is in AM relies on GRH.) @Turbo: The input is a set of integer polynomials, so defined with a finite number of bits. An obvious certificate for HN would be a solution to the system. But what Joshua says is that the description of such a solution is not necessarily representable with a finite number of bits. Thus we are far from having a *polynomial-size* certificate!
Bruno
CC BY-SA 3.0
2015-04-24T21:35:36.780Z
Note though that by definition, all the coordinates of a solution to an integer polynomial system are algebraic, thus belong to some number field. This means that they do admit a finite representation. Still, there is no reason for this finite representation to be of size polynomial in the input size.
Bruno
CC BY-SA 3.0
2015-04-24T21:47:07.847Z
@Bruno " if input is not in finite number of bits," I meant certificate is not in finite number of bits however as Bruno points, since it is a solution to algebraic equation there exists a finite basis with coefficients in $\Bbb Q$. Is it correct?
Turbo
CC BY-SA 3.0
2015-04-24T22:46:24.200Z
@Turbo: Yes, sorry, I was being silly before about infinite. It is finite, but need not be bounded by a polynomial. (Note: even if it had *rational* solutions, the bit-size of those solutions need not be bounded by a polynomial.)
Joshua Grochow
CC BY-SA 3.0
2015-04-25T01:59:37.180Z
@JoshuaGrochow Is there a concrete example where phenomena of small coefficient equation possessing large coefficient solutions (that cannot be tested succinctly with some underlying structure of the polynomial or solution).
Turbo
CC BY-SA 3.0
2015-04-25T07:56:30.753Z
@JoshuaGrochow I don't understand the part about NNL being in EXPSPACE unconditionally, but in P assuming blackbox PIT. We know that PIT is definitely in PSPACE(you can evaluate the circuit at all $d^n$ points where d is the degree of the multivariate polynomial and check if its uniformly zero). Why is this better bound not applicable for NNL if it is in P under the assumption that PIT is in P? (I will read the paper linked more carefully, but I wanted to get this simple question out of the way)
Nikhil
CC BY-SA 3.0
2015-04-25T14:30:02.717Z
@Nikhil: because PIT does not give an upper bound on NNL. Black-box hitting sets are what give the bound. The issue with enumerating over all possible hitting sets for NNL (the PSPACE algorithm for PIT) is that for each one, one must verify a certain property, and that verification is only known to be in EXPSPACE. If OTOH you can directly construct a guaranteed hitting set, basically you don't have to verify. You'll see when you read the paper.
Joshua Grochow
CC BY-SA 3.0
2015-04-25T17:07:57.897Z
@Turbo: I just added more details on resolution of singularities, in addition to more refs and links.
Joshua Grochow
CC BY-SA 3.0
2015-04-28T20:50:57.190Z
Quasigroup (and therefore group) isomorphism is in a slightly smaller complexity class, $\beta_2 \mathsf{FOLL}$, and is not hard for any complexity class containing the parity problem, according to http://eccc.hpi-web.de/report/2010/117/
argentpepper
CC BY-SA 3.0
2015-04-29T05:15:29.560Z
the McCurley survey paper ["Open Problems in Number Theoretic Complexity, II"](http://www.mccurley.org/papers/open.ps.gz)
Nikos M.
CC BY-SA 3.0
2015-04-29T13:52:04.880Z
@NikosM.: This is the same survey referenced in the original question...
Joshua Grochow
CC BY-SA 3.0
2015-04-29T16:18:23.287Z
it seems i missed that, saw it afterwards!
Nikos M.
CC BY-SA 4.0
2019-07-04T14:40:15.833Z
@JoshuaGrochow Is there a natural $PSPACE$ complete number theoretic problem?
Turbo
CC BY-SA 4.0
2019-12-08T07:59:57.500Z
@JoshuaGrochow Nullstellansatz is unknown to be in $NP$ because of certificate size or some other essential reason?
Turbo
CC BY-SA 4.0
2019-12-09T01:58:41.033Z
@T....: I suppose you could say it's because of certificate size, but in Koiran's algorithm, the randomness is used to estimate the size of the set of primes (up to some bound) over which the equations have solutions.
Joshua Grochow
CC BY-SA 3.0
2015-04-24T19:42:44.070Z
2018-04-18T15:52:03.660Z
2018-04-18T15:52:03.660Z
Joshua Grochow
<p>I am looking for a list about the known or unknown complexity of various number theoretic  /algebraic problems. For example,</p>

<ul>
<li>GCD in $NC^1$ is open,</li>
<li>factoring in $P$ is open,</li>
<li><a href="http://dl.acm.org/citation.cfm?id=299827" rel="nofollow noreferrer">computing sheaf cohomology is $\#P$-hard</a>,</li>
<li><a href="http://theory.cs.princeton.edu/complexity/" rel="nofollow noreferrer">Arora and Barak</a> state that a variant of factoring is $NP$-complete (though this is not clear based on the discussion at <a href="https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring">An NP-complete variant of factoring.</a>),</li>
<li><a href="https://eprint.iacr.org/2013/400.pdf" rel="nofollow noreferrer">Barbulescu et al's breakthrough work on discrete logarithms</a>.</li>
</ul>

<p>Adleman once published <a href="http://www.cse.iitk.ac.in/users/manindra/CS681/open-problems-in-number.pdf" rel="nofollow noreferrer">a list</a> focused on $P$ and $NP$ but it seems outdated. Mumford has <a href="http://www.dam.brown.edu/people/mumford/alg_geom/papers/1993a-WhatComputeAG-Bayer-DAM.pdf" rel="nofollow noreferrer">a paper</a> on what is computable in algebraic geometry without regard to complexity.</p>

<p>Does anyone know a list of (major) discoveries since these lists were published?</p>

<blockquote>
  <p>What are some problems of a number theoretic/algebraic flavor whose complexity classes are possibly already known (since the above lists were published), unknown but conjectured, or unknown and not conjectured?</p>
</blockquote>

<p>Some avenues of problems could be interpolation problems (univariate or multivariate, over various fields), Chinese remainder theorem, complexity of point counting over curves, etc.</p>

CC BY-SA 3.0
2015-04-24T03:07:58.963Z
Do you really want only problems whose complexity is not only not known, but isn't even speculated to be somewhere? That seems quite restrictive, e.g. integer factorization wouldn't satisfy that question since it is speculated to be in intermediate between P and $UP \cap coUP$... But I think (and hope) you mean a slightly more permissive question. It would be interesting to see such a list.
Joshua Grochow
CC BY-SA 3.0
2015-04-24T04:24:38.590Z
@JoshuaGrochow broadened.
Turbo
CC BY-SA 3.0
2015-04-24T09:17:09.157Z
No, it is an open problem whether it is anywhere in the NC hierarchy.
Emil Jeřábek
<cc.complexity-theory><big-list><algebra><open-problem>
List of number theoretic or algebraic problems in various complexity classes
Turbo
# List of number theoretic or algebraic problems in various complexity classes

(Asked by: username_0 on 2015-04-24)

I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example,

* GCD in $NC^1$ is open,
* factoring in $P$ is open,
* [computing sheaf cohomology is $\#P$-hard](http://dl.acm.org/citation.cfm?id=299827),
* [Arora and Barak](http://theory.cs.princeton.edu/complexity/) state that a variant of factoring is $NP$-complete (though this is not clear based on the discussion at [An NP-complete variant of factoring.](https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring)),
* [Barbulescu et al's breakthrough work on discrete logarithms](https://eprint.iacr.org/2013/400.pdf).

Adleman once published [a list](http://www.cse.iitk.ac.in/users/manindra/CS681/open-problems-in-number.pdf) focused on $P$ and $NP$ but it seems outdated. Mumford has [a paper](http://www.dam.brown.edu/people/mumford/alg_geom/papers/1993a-WhatComputeAG-Bayer-DAM.pdf) on what is computable in algebraic geometry without regard to complexity.

Does anyone know a list of (major) discoveries since these lists were published?

> What are some problems of a number theoretic/algebraic flavor whose complexity classes are possibly already known (since the above lists were published), unknown but conjectured, or unknown and not conjectured?

Some avenues of problems could be interpolation problems (univariate or multivariate, over various fields), Chinese remainder theorem, complexity of point counting over curves, etc.

**Tags:** cc.complexity-theory, big-list, algebra, open-problem

> **Comments:**
> **username_1**: Do you really want only problems whose complexity is not only not known, but isn't even speculated to be somewhere? That seems quite restrictive, e.g. integer factorization wouldn't satisfy that question since it is speculated to be in intermediate between P and $UP \cap coUP$... But I think (and hope) you mean a slightly more permissive question. It would be interesting to see such a list.  
> **username_0**: @JoshuaGrochow broadened.  
> **username_2**: No, it is an open problem whether it is anywhere in the NC hierarchy.  

---

## 2 answers

### Answer by username_1 on 2015-04-24. Score: 18 | Accepted answer

**Algebraic geometry**

* Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is [conjectured](http://gct.cs.uchicago.edu/gct5.pdf) to be in $\mathsf{P}$ (and is in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $\mathsf{PSPACE}$ over the rationals ([Forbes & Shpilka)](https://arxiv.org/abs/1712.09967) and then over arbitrary fields ([Guo, Saxena, & Sinhababu](https://arxiv.org/abs/1801.09275)).
* Testing whether a given set of polynomials has an algebraic dependence. This problem was recently shown to be in $\mathsf{AM} \cap \mathsf{coAM}$ by [Guo, Saxena, & Sinhababu](https://arxiv.org/abs/1801.09275) (improving the previous upper bound of $\mathsf{NP}^{\mathsf{\# P}}$ due to [Mittmann, Saxena, & Scheblechner](https://doi.org/10.1090/S0002-9947-2014-06268-5), also on the [arXiv](https://arxiv.org/abs/1202.4301)).
* There are [several](http://link.springer.com/article/10.1007%2Fs10208-012-9123-y) ([arXiv](https://arxiv.org/abs/0905.2212)) [new](http://www.sciencedirect.com/science/article/pii/S0747717109000133) algorithms for computing topological invariants of complex varieties (with various restrictions like smoothness, etc.). I believe for most of these the optimal upper bound is still open.
* Hilbert's Nullstellensatz (HN): given integer polynomials, decide if they have a common complex solution, is in $\mathsf{AM}$ assuming GRH ([Koiran](http://dx.doi.org/10.1006/jcom.1996.0019)). It is unknown if it is in $\mathsf{NP}$.
* Algorithms for resolution of singularities of algebraic varieties in characteristic zero. The [current best time upper bound](http://www.ams.org/mathscinet-getitem?mr=2838220), due to [Bierstone, Grigoriev, Milman, and Włodarczyk](http://logic.pdmi.ras.ru/~grigorev/pub/hiron-complex_journal.pdf) is $\mathcal{E}^{d+3}$ where $d$ is the dimension of the variety and $\mathcal{E}^{\bullet}$ is the [Grzegorczyk hierarchy of primitive recursive functions](http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy). There aren't particularly good (any?) lower bounds on this problem, but for a seemingly much simpler problems related lower bounds are known, namely: There are ideals in $n$ variables generated in degree at most $n$ that require $\mathcal{E}^{n+1}$ such generators. So the current upper bound for resolution of singularities may not be far from the truth, but little is really known.

**Isomorphism problems**

* Many problems on permutation groups - such as coset intersection, permutation group isomorphism, etc. - are in $\mathsf{NP} \cap \mathsf{coAM}$, but it is unknown if they are in $\mathsf{NP} \cap \mathsf{coNP}$, and it is suspected that they are not in $\mathsf{P}$. Graph Isomorphism reduces to most of those problems, so a better upper bound on them implies a better upper bound on GI.
* In particular, for permutation group isomorphism, the [current best upper bound](http://link.springer.com/chapter/10.1007%2F978-3-642-31594-7_5) is $2^{O(n)}|G|$, and it is open if it can be done in $2^{O(n)}$ time (depending only on the degree of the permutation group and not on its order), let alone [quasi-poly time like GI and coset intersection](https://arxiv.org/abs/1512.03547).
* Group Isomorphism where groups are given by multiplication tables is known to be in $\mathsf{TIME}(n^{O(\log n)})$, but is suspected to be in $\mathsf{P}$. Known to be in $\mathsf{P}$ for [several](http://arxiv.org/abs/1309.1776) [classes](http://dx.doi.org/10.4230/LIPIcs.STACS.2012.453) of [groups](https://arxiv.org/abs/1010.5466) (update 4/18/18: and a [couple](https://doi.org/10.1016/j.jalgebra.2016.12.007) ([arXiv](https://arxiv.org/abs/1508.03033)) [more](http://dx.doi.org/10.1007/978-3-662-48971-0_49) ([arXiv](http://arxiv.org/abs/1507.01917))), but not in general.

**Other**

* Update 4/18/18: Tensor rank over any field $\mathbb{F}$ is $\exists \mathbb{F}$-complete ([Schaefer & Stefankovic](https://arxiv.org/abs/1612.04338)). ~~Is tensor rank over $\mathbb{Q}$ in $\mathsf{NP}$?~~ It is known to be $\mathsf{NP}$-hard ([Håstad](http://dx.doi.org/10.1016/0196-6774(90)90014-6)), and over finite fields it is in $\mathsf{NP}$.
* More generally, many problems on tensors over $\mathbb{Q}$ are $\mathsf{NP}$-hard but not known to be in $\mathsf{NP}$ ([Hillar and Lim](http://dx.doi.org/10.1145/2512329), also on the [arXiv](http://arxiv.org/abs/0911.1393)).

It would (somewhat sadly) seem that the Adleman-McCurley survey, despite being 21 years old, is pretty up to date in terms of number-theoretic problems, with the exception of the fact that we now know that [$\mathsf{PRIMES}$ is in $\mathsf{P}$](http://dx.doi.org/10.4007%2Fannals.2004.160.781)...

> **Comments:**
> **username_0**: I am surprised HN is in NP is unknown. All you have to do is check solution for each polynomial right?  
> **username_0**: IWhat is the gap in resolution of singularities?  
> **username_1**: @username_0: For HN, the polynomials are integer polynomials, but the solutions are allowed to be complex numbers that need not even be expressible by a finite number of bits, let alone a polynomial number of bits. Also, to even get AM I think you need GRH.  
> **username_0**: Ok it is not clear to me, if input is not in finite number of bits, how do you define its complexity?  
> **username_4**: (First I confirm the proof that HN is in AM relies on GRH.) @username_0: The input is a set of integer polynomials, so defined with a finite number of bits. An obvious certificate for HN would be a solution to the system. But what Joshua says is that the description of such a solution is not necessarily representable with a finite number of bits. Thus we are far from having a *polynomial-size* certificate!  
> **username_4**: Note though that by definition, all the coordinates of a solution to an integer polynomial system are algebraic, thus belong to some number field. This means that they do admit a finite representation. Still, there is no reason for this finite representation to be of size polynomial in the input size.  
> **username_0**: @username_4 " if input is not in finite number of bits," I meant certificate is not in finite number of bits however as username_4 points, since it is a solution to algebraic equation there exists a finite basis with coefficients in $\Bbb Q$. Is it correct?  
> **username_1**: @username_0: Yes, sorry, I was being silly before about infinite. It is finite, but need not be bounded by a polynomial. (Note: even if it had *rational* solutions, the bit-size of those solutions need not be bounded by a polynomial.)  
> **username_0**: @JoshuaGrochow Is there a concrete example where phenomena of small coefficient equation possessing large coefficient solutions (that cannot be tested succinctly with some underlying structure of the polynomial or solution).  
> **username_5**: @JoshuaGrochow I don't understand the part about NNL being in EXPSPACE unconditionally, but in P assuming blackbox PIT. We know that PIT is definitely in PSPACE(you can evaluate the circuit at all $d^n$ points where d is the degree of the multivariate polynomial and check if its uniformly zero). Why is this better bound not applicable for NNL if it is in P under the assumption that PIT is in P? (I will read the paper linked more carefully, but I wanted to get this simple question out of the way)  
> **username_1**: @username_5: because PIT does not give an upper bound on NNL. Black-box hitting sets are what give the bound. The issue with enumerating over all possible hitting sets for NNL (the PSPACE algorithm for PIT) is that for each one, one must verify a certain property, and that verification is only known to be in EXPSPACE. If OTOH you can directly construct a guaranteed hitting set, basically you don't have to verify. You'll see when you read the paper.  
> **username_1**: @username_0: I just added more details on resolution of singularities, in addition to more refs and links.  
> **username_6**: Quasigroup (and therefore group) isomorphism is in a slightly smaller complexity class, $\beta_2 \mathsf{FOLL}$, and is not hard for any complexity class containing the parity problem, according to http://eccc.hpi-web.de/report/2010/117/  
> **username_3**: the McCurley survey paper ["Open Problems in Number Theoretic Complexity, II"](http://www.mccurley.org/papers/open.ps.gz)  
> **username_1**: @NikosM.: This is the same survey referenced in the original question...  
> **username_3**: it seems i missed that, saw it afterwards!  
> **username_0**: @JoshuaGrochow Is there a natural $PSPACE$ complete number theoretic problem?  
> **username_0**: @JoshuaGrochow Nullstellansatz is unknown to be in $NP$ because of certificate size or some other essential reason?  
> **username_1**: @T....: I suppose you could say it's because of certificate size, but in Koiran's algorithm, the randomness is used to estimate the size of the set of primes (up to some bound) over which the equations have solutions.  

---

### Answer by username_3 on 2015-04-27. Score: 4

Adding a few more with emphasis on Galois theory and computational Galois theory (see [related question on cs.SE](https://cs.stackexchange.com/a/41740/17369)):

The computational complexity of determining if a given monic irreducible polynomial over the integers $\mathbb{Z}$, is soluble by radicals is in $\mathbb{P}$ Ref ["Solvability by Radicals Is in Polynomial Time", S. Landau G.L Miller 1984](https://www.cs.cmu.edu/~glmiller/Publications/Papers/LaMi85.pdf)

> According to a paper Upper bounds on the complexity of some Galois
> Theory problems by Arvind and Kurur
> [here](http://www.cse.iitk.ac.in/users/ppk/research/publication/AK2003.pdf),
> a theorem of Landau gives an exponential upper bound in the size of
> the polynomial under a certain definition of size. More precisely, her
> theorem gives a polynomial bound in terms of the size of the Galois
> group and the size of the polynomial. But the size of the group can be
> exponential in the size of the polynomial. They show if the Galois
> group is solvable, then the order can be computed by a randomized
> polynomial time algorithm with an $NP$ oracle.

reproduced from [linked question on MO](https://mathoverflow.net/a/149508/50427)


---

