12
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Apr 24 '15 at 3:07
  • $\begingroup$ @JoshuaGrochow broadened. $\endgroup$ – T.... Apr 24 '15 at 4:24
  • $\begingroup$ Is GCD known to be in logspace? $\;$ $\endgroup$ – user6973 Apr 24 '15 at 7:32
  • 4
    $\begingroup$ No, it is an open problem whether it is anywhere in the NC hierarchy. $\endgroup$ – Emil Jeřábek supports Monica Apr 24 '15 at 9:17
18
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am surprised HN is in NP is unknown. All you have to do is check solution for each polynomial right? $\endgroup$ – T.... Apr 24 '15 at 19:46
  • $\begingroup$ IWhat is the gap in resolution of singularities? $\endgroup$ – T.... Apr 24 '15 at 19:47
  • 4
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Apr 24 '15 at 19:49
  • 2
    $\begingroup$ (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! $\endgroup$ – Bruno Apr 24 '15 at 21:26
  • 3
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Apr 25 '15 at 14:30
4
$\begingroup$

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

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