Redundanz und Struktur von Rechenproblemen

11

Es wird allgemein angenommen, dass einige Rechenprobleme wie der Graphisomorphismus nicht NP-vollständig sein können, da sie nicht genügend Struktur oder Redundanz besitzen, um rechenintensiv (NP-hart) zu sein. Ich interessiere mich für die verschiedenen formalen Begriffe für die Struktur von Rechenproblemen und Redundanzmaßnahmen.

Was sind die wichtigsten bekannten Ergebnisse über solche formalen Begriffe für Rechenprobleme? Eine aktuelle Übersicht über solche Begriffe wäre sehr schön.

BEARBEITEN : Gepostet auf MathOverflow

cc.complexity-theory graph-isomorphism Mohammad Al-Turkistany
quelle

Antworten:

4

Eigentlich denke ich, dass das Phänomen hier ist, dass GI in gewissem Sinne zu viel Struktur hat. In gewisser Weise führt die gruppentheoretische Natur ihrer Zeugen zum -Algorithmus für GI und ist einer der technischen Beweise dafür, warum Menschen glauben, dass GI nicht N P- vollständig ist. Ich denke hier, dass es so viel Struktur gibt, dass das Problem "zu starr" ist, um willkürliches N P zu codierencoAMNPNP -Probleme .

NP

(Auf der anderen Seite, Gruppenisomorphismus scheint noch mehr strukturiert als GI, noch keine Zählung-to-Entscheidung Reduktion wird für die Gruppe iso bekannt Vielleicht sagt dies , dass GI ist in Art einer „genau richtig“ Ebene der Struktur -. Zu strukturierenden NP-vollständig sein, aber unstrukturiert genug, um eine Reduzierung des Zählens bis zur Entscheidung zu ermöglichen.)

Joshua Grochow
quelle
GI ist also in gewissem Sinne nicht "zufällig" genug, um die NP-Vollständigkeit zu erfassen. Gibt es eine formale Vorstellung, die einen solchen Mangel an Zufälligkeit des GI-Problems erfasst?
Mohammad Al-Turkistany
1
Ja, eine solche Vorstellung ist, dass GI nicht NP-vollständig ist! :-) (Es sei denn, die Polynomhierarchie bricht zusammen.)
Scott Aaronson
Jacobo Toran erklärt: "Es gibt eine verbreitete Überzeugung, dass GI nicht genügend Struktur oder Redundanz enthält, um für NP schwierig zu sein", SIAM Journal on Computing, 33 (5), 1093–1108. Das Problem ist, dass wir nicht wissen, wie wir die Nicht-NP-Härte natürlicher NP-Probleme nachweisen können.
Mohammad Al-Turkistany
Ich denke, vielleicht sind Torans Aussage und meine zwei Seiten derselben Medaille: Meine sagt, dass einzelne Probleminstanzen zu strukturiert sind, und ein Ergebnis davon ist, dass die Gesamtsprache GI nicht redundant genug ist (Torans Aussage). Meiner Ansicht nach. Ohne Jacobo wirklich zu fragen, ist es schwer zu sagen.
Joshua Grochow