Liste zahlentheoretischer oder algebraischer Probleme in verschiedenen Komplexitätsklassen

12

Ich suche eine Liste über die bekannte oder unbekannte Komplexität verschiedener zahlentheoretischer / algebraischer Probleme. Beispielsweise,

Adleman hat einmal eine Liste veröffentlicht, die sich auf und aber sie scheint veraltet zu sein. Mumford hat eine Arbeit darüber, was in der algebraischen Geometrie ohne Rücksicht auf die Komplexität berechenbar ist.N PPNP

Kennt jemand eine Liste von (Haupt-) Entdeckungen, seitdem diese Listen veröffentlicht wurden?

Was sind einige Probleme einer zahlentheoretischen / algebraischen Variante, deren Komplexitätsklassen möglicherweise bereits bekannt sind (seit die obigen Listen veröffentlicht wurden), unbekannt, aber vermutet oder unbekannt und nicht vermutet?

Einige Problemwege könnten Interpolationsprobleme (univariate oder multivariate über verschiedene Felder), der chinesische Restsatz, die Komplexität der Punktzählung über Kurven usw. sein.

T ....
quelle
Wollen Sie wirklich nur Probleme, deren Komplexität nicht nur nicht bekannt ist, sondern auch nicht spekuliert wird, irgendwo zu sein? Das scheint ziemlich restriktiv, zB Integer - Faktorisierung würde diese Frage nicht befriedigen , da es wird spekuliert, in der Mitte zwischen P und seine ... Aber ich denke (und hofft) Sie etwas tolerante Frage bedeuten. Es wäre interessant, eine solche Liste zu sehen. UPcoUP
Joshua Grochow
@ JoshuaGrochow erweitert.
T ....
Ist bekannt, dass sich GCD im Logspace befindet?
4
Nein, es ist ein offenes Problem, ob es sich irgendwo in der NC-Hierarchie befindet.
Emil Jeřábek unterstützt Monica am

Antworten:

18

Algebraische Geometrie

  • Derzeit ist nur bekannt, dass das Noether-Normalisierungs-Lemma (NNL) für explizite Varietäten in (wie allgemeines NNL) enthalten ist, es wird jedoch vermutet , dass es sich bei P um P handelt (und P unter der Annahme, dass PIT eine Blackbox sein kann) derandomisiert). Update 18.04.18: Es wurde kürzlich gezeigt, dass für die Sorte ¯ V PEXPSPACEPPVP¯ um über die Rationen ( Forbes & Shpilka) und dann über beliebige Felder ( Guo, Saxena & Sinhababu ).PSPACE

  • Testen, ob eine gegebene Menge von Polynomen eine algebraische Abhängigkeit hat. Dieses Problem wurde vor kurzem in seine gezeigten AMcoAM von Guo, Saxena, & Sinhababu (obere der Verbesserung der früheren gebundenen aufgrund Mittmann, Saxena, & Scheblechner , auch auf der arXiv ).NP#P

  • Es gibt mehrere ( arXiv ) neue Algorithmen zur Berechnung topologischer Invarianten komplexer Sorten (mit verschiedenen Einschränkungen wie Glätte usw.). Ich glaube, für die meisten davon ist die optimale Obergrenze noch offen.

  • Hilbert Nullstellensatz (HN): integer Polynome gegeben, zu entscheiden , ob sie eine gemeinsame komplexe Lösung haben, ist in unter der Annahme , GRH ( Koiran ). Es ist nicht bekannt, ob es sich um N P handelt .AMNP

  • Algorithmen zur Auflösung von Singularitäten algebraischer Varietäten im Merkmal Null. Die aktuelle Obergrenze für die beste Zeit aufgrund von Bierstone, Grigoriev, Milman und Włodarczyk ist wobei d die Dimension der Sorte und E die Grzegorczyk-Hierarchie der primitiven rekursiven Funktionen ist . Es sind nicht besonders gut (welche?) Untere Schranken für dieses Problem, aber für ein scheinbar viel einfacheren Probleme im Zusammenhang untere Grenzen bekannt sind, nämlich: Es gibt Ideale in n Variablen in Grad erzeugte höchstens n , die erfordern , E n + 1Ed+3dEnnEn+1solche Generatoren. Die derzeitige Obergrenze für die Auflösung von Singularitäten ist vielleicht nicht weit von der Wahrheit entfernt, aber es ist wirklich wenig bekannt.

Isomorphismusprobleme

  • Viele Probleme bei Permutationsgruppen - wie Coset-Schnittmenge, Permutationsgruppen-Isomorphismus usw. - liegen in , aber es ist unbekannt, ob sie in N Pc o N P liegen , und es wird vermutet, dass sie vorliegen nicht in sind P . Der Graphisomorphismus reduziert sich auf die meisten dieser Probleme, sodass eine bessere Obergrenze für sie eine bessere Obergrenze für den GI impliziert.NPcoAMNPcoNPP

  • Insbesondere für Permutation Gruppenisomorphismus, die derzeit beste obere Schranke ist 2O(n)|G|, und es ist offen, ob es in -Zeit (abhängig nur vom Grad der Permutationsgruppe und nicht von ihrer Reihenfolge) durchgeführt werden kann, geschweige denn in Quasi-Poly-Zeit wie GI und Coset-Schnittmenge .2O(n)

  • Der Gruppenisomorphismus, bei dem Gruppen durch Multiplikationstabellen angegeben werden, ist bekanntermaßen in , wird jedoch in P vermutet . Bekanntermaßen in P für mehrere Klassen von Gruppen (Update 18.04.18: und ein paar ( arXiv ) mehr ( arXiv )), aber nicht im Allgemeinen.TIME(nO(logn))PP

Andere

  • Update 4/18/18: Tensor Rang über ein beliebiges Feld ist F -komplette ( Schaefer & Stefankovic ). Liegt der Tensorrang in N P über Q ? Es ist bekannt, dass N P -hard ( Håstad ) und über endliche Felder ist es in N P .FFQNPNPNP

  • Allgemeiner gesagt , viele Probleme auf Tensoren über sind N P -hard aber nicht bekannt, dass sie in N P ( Hillar und Lim , auch auf dem arXiv ).QNPNP

Es scheint (etwas traurig), dass die Adleman-McCurley-Umfrage, obwohl sie 21 Jahre alt ist, in Bezug auf zahlentheoretische Probleme ziemlich aktuell ist, mit Ausnahme der Tatsache, dass wir jetzt wissen, dass PRIMESP

Joshua Grochow
quelle
Ich bin überrascht, dass HN in NP unbekannt ist. Alles was Sie tun müssen, ist die Lösung für jedes Polynom zu überprüfen, oder?
T ....
IWas ist die Lücke in der Auflösung von Singularitäten?
T ....
4
@Turbo: Für HN sind die Polynome ganzzahlige Polynome, aber die Lösungen dürfen komplexe Zahlen sein, die nicht einmal durch eine endliche Anzahl von Bits ausgedrückt werden müssen, geschweige denn durch eine polynomielle Anzahl von Bits. Ich denke, Sie brauchen GRH, um überhaupt morgens zu sein.
Joshua Grochow
2
(Zuerst bestätige ich, dass HN in AM ist und sich auf GRH stützt.) @Turbo: Die Eingabe ist eine Menge von ganzzahligen Polynomen, die mit einer endlichen Anzahl von Bits definiert sind. Ein offensichtliches Zertifikat für HN wäre eine Lösung für das System. Aber was Joshua sagt, ist, dass die Beschreibung einer solchen Lösung nicht unbedingt mit einer endlichen Anzahl von Bits darstellbar ist. Wir sind also weit davon entfernt, ein polynomisches Zertifikat zu haben!
Bruno
3
@ Nikhil: weil PIT keine Obergrenze für NNL gibt. Black-Box-Schlagsets sind das, was die Grenze gibt. Das Problem bei der Aufzählung aller möglichen Treffersätze für NNL (der PSPACE-Algorithmus für PIT) besteht darin, dass für jeden eine bestimmte Eigenschaft überprüft werden muss und dass die Überprüfung nur in EXPSPACE erfolgt. Wenn Sie mit OTOH direkt einen garantierten Schlagsatz konstruieren können, müssen Sie ihn im Grunde nicht verifizieren. Sie werden sehen, wenn Sie die Zeitung lesen.
Joshua Grochow