Der Nachweis, dass das Graphisomorphismusproblem nicht

10

Das Graphisomorphismusproblem ist eines der am längsten bestehenden Probleme, die sich der Klassifizierung in oder N P- vollständige Probleme widersetzten. Wir haben Beweise dafür, dass es nicht N P- vollständig sein kann. Erstens kann der Graphisomorphismus nicht N P -vollständig sein, es sei denn, die Polynomhierarchie [1] kollabiert auf die zweite Ebene. Außerdem ist die Zählversion [2] von GI eine Polynomzeit-Turing-Entsprechung zu ihrer Entscheidungsversion, die für kein bekanntes N P- vollständiges Problem gilt. Die Zählversion von N P -vollständigen Problemen scheint eine viel höhere Komplexität zu haben. Schließlich ist das Ergebnis der Niedrigkeit [3] von GI in Bezug auf P P (PNPNPNPNPNPPP ist nicht bekannt, dass P P G I = P P ) für ein N P- vollständiges Problem gilt. Das Lowness-Ergebnis von GI wurde auf S P P G I = S P P verbessert,nachdem Arvind und Kurur bewiesen hatten, dass GI in S P P vorliegt[4].PPGI=PPNPSPPGI=SPPSPP

Welche anderen (jüngsten) Ergebnisse können weitere Beweise dafür liefern, dass GI nicht vollständig sein kann?NP

Ich habe die Frage auf Mathoverflow gepostet, ohne eine Antwort zu erhalten.

[1]: Uwe Schöning, "Graphisomorphismus ist in der niedrigen Hierarchie", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124

[2]: R. Mathon, "Ein Hinweis auf das Problem der Zählung von Isomorphismusgraphen", Information Processing Letters, 8 (1979), S. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graphisomorphismus ist für PP gering", Computational Complexity 2 (4): 301–330

[4]: V. Arvind und P. Kurur. Der Graphisomorphismus ist in SPP, ECCC TR02-037, 2002.

Mohammad Al-Turkistany
quelle
8
Wie viel mehr Beweise brauchen Sie? Lassen Sie mich die Frage umdrehen: Welche Beweise gibt es dafür, dass GI nicht in P ist?
Lance Fortnow
@LanceFortnow Ich denke, die Tatsache, dass wir nicht einmal einen quasi-polynomiellen Zeitalgorithmus für GI haben, ist der beste Beweis dafür, dass GI nicht in . Kennen Sie andere? P
Mohammad Al-Turkistany
2
Indizien dafür, dass GI in P ist, ist, dass (afaik / afact) niemand Nicht-P-harte Instanzen konstruieren kann (auch nicht zufällig?) und es scheint nicht einmal (vermutete) Kandidaten zu geben. ps diese Frage scheint nahe an der derzeit bekannten Härte von GI
vzn
1
@vzn Es ist HW Problem zu beweisen , dass , wenn , alle Sprachen in P mit Ausnahme von und Σ * seien N P -komplette (dies ist unter Karp Abschlägen). P=NPPΣNP
Mohammad Al-Turkistany
3
@Arul Siehe meinen Kommentar zu VZN. Wenn P = NP ist, muss GI unter Karp-Reduktion NP-vollständig sein.
Mohammad Al-Turkistany

Antworten:

11

GIQPGINPNPQP=DTIME(npolylogn)EXP=NEXPEXPNEXPGINP

Andras Farago
quelle