List of number theoretic or algebraic problems in various complexity classes

Question

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,
• Arora and Barak 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.),
• Barbulescu et al's breakthrough work on discrete logarithms.

Adleman once published a list focused on $P$ and $NP$ but it seems outdated. Mumford has a paper 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.

Answer 1

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 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) and then over arbitrary fields (Guo, Saxena, & Sinhababu).

• 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 (improving the previous upper bound of $\mathsf{NP}^{\mathsf{\# P}}$ due to Mittmann, Saxena, & Scheblechner, also on the arXiv).

• There are several (arXiv) new 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). 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, due to Bierstone, Grigoriev, Milman, and Włodarczyk 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. 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 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.

• 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 classes of groups (update 4/18/18: and a couple (arXiv) more (arXiv)), but not in general.

Other

• Update 4/18/18: Tensor rank over any field $\mathbb{F}$ is $\exists \mathbb{F}$-complete (Schaefer & Stefankovic). Is tensor rank over $\mathbb{Q}$ in $\mathsf{NP}$? It is known to be $\mathsf{NP}$-hard (Håstad), 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, also on the arXiv).

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

Answer 2

Adding a few more with emphasis on Galois theory and computational Galois theory (see related question on cs.SE):

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

According to a paper Upper bounds on the complexity of some Galois Theory problems by Arvind and Kurur here, 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