Probleme in der quasi-polynomiellen Zeit, die möglicherweise in P liegen könnten (ohne Zusammenbrüche zu verursachen oder weit verbreitete Überzeugungen zu verletzen)

8

Was sind einige Beispiele für Probleme mit quasi-Polynomzeit ( ) Algorithmen , die möglicherweise in sein könnte P . Mit anderen Worten, sie befinden sich in Q P aus keinem offensichtlichen Grund, außer dass niemand einen Polynom-Zeit-Algorithmus gefunden hat?QPPQP

Diese Frage wird durch das aktuelle Ergebnis des Graphisomorphismus motiviert (was eine gültige Antwort auf diese Frage ist).

Einige Nichtbeispiele sind

  • Die Suche nach einer Clique der Größe in einem Diagrammlog100n
  • Die Suche nach einem Weg der Größe in einem Diagrammlog100n
  • Lösen der k-Summe nach k=log100n
  • Minimaler dominierender Satz in einem Turnier

Jedes dieser Probleme in würde die Exponentialzeithypothese (ETH) verletzen.P

Anonanon
quelle
Es ist bekannt, dass der Graphisomorphismus für Turniere in quasi-polynomieller Zeit vorliegt, es ist jedoch nicht bekannt, dass er in . Die Existenz von Polynomzeitalgorithmen würde keine bekannte komplexitätstheoretische Vermutung verletzen. P
Mohammad Al-Turkistany

Antworten:

12

Gruppenisomorphismus! Obwohl Ricky Demer viele (wenn auch sicherlich nicht alle) Details dazu gegeben hat, gibt es einen wichtigen Punkt, den ich hervorheben möchte, insb. angesichts der angegebenen Motivation für die Frage, nämlich:

Das Einfügen des Gruppenisomorphismus in ist ein wesentliches Hindernis für das Einfügen des Graphisomorphismus in P.PP

Der Gruppenisomorphismus (wenn durch Multiplikationstabellen angegeben) reduziert sich auf den Graphisomorphismus, so dass das oben Gesagte technisch immer zutraf. Aber als Graph Iso bei Es war so weit von Group Isos2(logn)2 entfernt,dass eindeutig andere Hindernisse im Weg standen. Wenn Graph Iso in Zeit2(logn) O ( 1 ) , ist Gruppenisomorphismus dann ein viel unmittelbar relevant Hindernis zu bringen Graphisomorphie inP. Dies würde insbesondere darauf hindeuten, dass Babais Algorithmus einen Großteil [1] der Kombinatorik von GI handhabt, und das Problem liegt nun in der harten Algebra. (Nicht, dass es in GI keine harte Algebra gibt, aber GroupIso handeltper Definitionvon Algebra.)2O~(n)2(logn)22(logn)O(1)P

>2

Joshua Grochow
quelle
Nett. Ihre Antwort ist perfekt als Antwort auf diesen Beitrag geeignet: cstheory.stackexchange.com/questions/32160/…
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Nur wenn Sie denken, dass Group Iso nicht in P ist ... Auch Thomas Kimpels Antwort auf diese Frage trifft in diesem Punkt bereits eine Art Treffer (aber zu der Zeit, wie ich sagte, war GI so weit davon entfernt GroupIso dass es im Prinzip andere Gründe dafür geben könnte, nicht in P) zu sein.
Joshua Grochow
10

2log2nn

David Eppstein
quelle
7

Gruppenisomorphismus ist ein weiteres anständig bekanntes Problem, von dem bekannt ist
, dass es in quasi-polynomieller Zeit lösbar ist. Das Ergebnis kann verallgemeinert werden
auf andere endliche Objekte , die „erweitern“ Gruppen in einem geeigneten Sinne -
[ commutative Halbringe mit der Nullprodukteigenschaft ] und kommutativ Gruppoide
sind beide nicht nahe genug, aber [ Θ (1) -Länge Tupel von Gruppen mit Beschriftungen auf einigen Tupeln
von Gruppenelementgruppen (die nicht unbedingt aus derselben Gruppe stammen) funktionieren alle.
(Das ist ziemlich weit gefasst, da beschriftete Tupel von Singletons Codierungsfunktionen ermöglichen
und dann Tupel von Gruppen getrennt werden könnenSkalare und Vektoren .)

Für diese Antwort werden Gruppen durch Cayley-Tabellen angegeben . Denken Sie daran, dass die Probleme, die ich
erwähnen werde , nur "wirklich" in SUBEXP bekannt sind, wenn entweder [ihre zugrunde liegenden Gruppen
nicht unbedingt alle abelisch sind] oder [sie "eine ausreichend große Menge" an Kennzeichnungen haben können wird
nicht von [einer "kleinen" Anzahl von [[Untergruppen direkter Summen dieser Gruppen] und / oder
[Funktionen von und zu solchen Untergruppen, die sich über Addition verteilen]]] umfasst, da sonst
alles durch Ausdrücken von Dingen exponentiell komprimiert werden könnte In Bezug auf Generierungssätze würde
in diesem Fall die Angabe der vollständigen Tabellen im Wesentlichen dem Auffüllen der Eingabe gleichkommen.

A, B.





Ferner (noch Reingold verwendet wird ), logspace Maschinen können solche morphisms berechnen gegebenen
2-Wege - Zugang zu solchen Zeugen, und wenn sie zusätzlich zu einem zufälligen Band 2-Wege - Zugang haben,
dann können sie geben [[a [Proof-of-Wissen in Bezug auf einen Extraktor, der einen 2-Wege-Lesezugriff
auf das hat, was er bereits ausgegeben hat] eines solchen Zeugen für Isomorphismus] mit den gleichen Eigenschaften
wie der übliche ZK P oK für Graphisomorphismus] auf einen Logspace-Verifizierer mit 2-Wege-Lesezugriff zu
seiner eigenen Zufälligkeit und den Botschaften des Prüfers. In ähnlicher Weise die HVSZK Proofsystem für Graph
nicht trägt -isomorphism über im Wesentlichen unverändert auf Objekte des Typs dieses Absatzes ausmacht.



log 2 (Kardinalität der Gruppe)

Infolgedessen bekommt man das Zeug, das vom einfach zu formulierenden
"Untergruppen-Isomorphismus" bis zur moderaten "Mindestanzahl von Elementen,
die mit einer gegebenen Teilmenge einer abelschen Gruppe kombiniert werden können , um die gesamte Gruppe zu erzeugen" reicht.
auf die absichtlich kompliziert zu Staat
„benötigen eine Domäne , deren Da Skalare nur zur Bildung eines rng und eine Codomäne mit
nicht unbedingt kommutativer "Vektor" -Adddition gibt es mehr als 3 Algebra- Homomorphismen, so dass die Karte auf Skalaren nicht die Null r istng Morphismus und die Karte auf "Vektoren" ist injektiv? "
sind alle in GC(O(2), Logspace)und damit insbesondere in quasi-polynomieller Zeit lösbar.


Abgesehen von der Tatsache, dass [ seit 2011 bedeutende Arbeiten an dem Problem den Exponenten der Laufzeit für allgemeine Gruppen "lediglich" halbiert und den Exponenten der Laufzeit für lösbare Gruppen geviertelt haben ], sind
mir keine Beweise dafür bekannt, dass solche Probleme nicht auftreten sollten Schüler: Der


Beweis, dass die Probleme, um die es in dieser Antwort geht, "nicht so schwer" sind:

Ich habe bereits das ZKPoK- und HVSZK-Proof-System erwähnt.
Immer wenn "nicht zu viele" nicht-isomorphe Objekte vorhanden sind, reicht es aus, dem Prüfer eine "nicht zu lange" Hinweiszeichenfolge zu geben und die Beweise einen Zeiger auf die darin enthaltenen Stellen zu lassen, um zusätzlich
die Komplemente der Art des Problems zu überprüfen Die Antwort war ungefähr vor diesem Satz.
(Der Zeiger zeigt an, wo die Hinweiszeichenfolge [2 Referenzobjekte
, zu denen die Eingabeobjekte isomorph sind] und die Antworten für diese gibt.)
Durch diese Antwort wird an die Anzahl der nicht isomorphen Gruppen gebunden (die ich nicht kann) beweisen), wann immer die markierten Tupel von der Kombination von
[
[O(2)]]
nO((log(n))2)

O(log 6 n)O(log 2 n)




Gemeinschaft
quelle
Factoring, diskretes Protokoll?
Es ist nicht bekannt, dass diese von klassischen Computern in quasi-polynomieller Zeit lösbar sind.
@Arul: Factoring reduziert sich auf Ring-ISO, wenn die Ringe von Generatoren und Relationen angegeben werden. Nicht, wenn sie durch ihre vollständigen Multiplikationstabellen gegeben sind (im letzteren Fall hat Ring Iso wie Group Iso einen Quasi-Poly-Zeit-Algorithmus).
Joshua Grochow
1
@JoshuaGrochow 'Factoring reduziert sich auf Ring-ISO, wenn die Ringe von Generatoren und Relationen angegeben werden' Könnten Sie die Reduktion oder Referenz teilen?
1
@Arul: Eigentlich ist etwas Stärkeres als das, was ich vorher geschrieben habe, wahr. Das Faktorisieren reduziert sich auf Ring-Iso, selbst wenn der Ring durch eine lineare Basis und Strukturkoeffizienten gegeben ist (siehe Abschnitt 2 von Kayal-Saxena, was dies bedeutet). Tabellenmodell bedeutet, dass die Eingabe buchstäblich alle Elemente des Rings auflistet (was möglich ist, wenn der Ring endlich ist) und für jedes Paar angibt, was ihre Summe und was ihr Produkt ist.
Joshua Grochow
5

H:=(V,E2V)HVE

HT

TH

Der bekannteste Algorithmus ist ein quasi-polynomieller Zeitalgorithmus (der erste ist der von Fredman und Khachiyan http://dx.doi.org/10.1006/jagm.1996.0062

Das Problem ist als monotone boolesche Dualität oder Hypergraph-Dualität bekannt, und mehrere Aufzählungsprobleme lassen sich auf dieses Problem reduzieren oder sind diesem äquivalent (zum Beispiel entspricht die Aufzählung minimal dominierender Mengen diesem Problem). Es wird tatsächlich angenommen, dass es in P. ist.

M. kanté
quelle