Wovon ernähren sich Dichotomiesätze?

10

Es ist bekannt, dass bestimmte Klassen von NP- Problemen Dichotomiesätze haben , die garantieren, dass jede Aufgabe in der Klasse entweder NP- vollständig oder in P ist . Das bekannteste derartige Ergebnis ist Schäfers Dichotomiesatz zusammen mit einer Reihe von Verallgemeinerungen.

Mein Verständnis ist, dass es nicht wirklich einfach ist, diese Dichotomiesätze zu beweisen. Ich frage mich, ob es eine relativ kurze Erklärung dafür gibt, warum bestimmte Klassen Dichotomiesätze haben, während andere dies nicht tun. Was ist die wesentliche Problemstruktur, die diese Theoreme ermöglicht? Oder vielleicht gibt es keine so klar verstandene Struktur, sondern es ist in jedem Fall ein Rätsel, warum die Klasse einen Dichotomiesatz hat oder nicht?

cc.complexity-theory np descriptive-complexity Andras Farago
quelle
2
Gute Frage. Ich denke, eine Intuition ist, dass wir die Probleme auf eine Klasse beschränken, die nette Beschreibungen hat.
Kaveh
5
Dies ist keine Antwort, weist aber vielleicht darauf hin, wo eine Antwort sein könnte (nicht): Wenn die Klasse der Probleme groß genug ist, um alle (oder sogar nur eine bestimmte Teilmenge davon) , dann Ladners Der Satz gilt und es wird keine Zweiteilung geben. Eine Klasse mit Dichotomie muss also zumindest so strukturiert sein, dass Ladner vermieden wird ...NP
Joshua Grochow
1
Dichotomien treten auf, wenn die Sprache zu grob ist, um feine Unterscheidungen zu treffen.
András Salamon

Antworten:

2

Für den Fall des Schäfer-Dichotomie-Theorems steht informell die universelle Ausdruckskraft von Booleschen CNF-Formeln, die aus nicht-Schaefer-logischen Beziehungen aufgebaut sind, hinter der Dichotomie. Jede logische Beziehung ist durch eine solche Formel unter Verwendung eines existenziellen Quantifizierers definierbar. Dies wird formal in Schäfers Ausdruckssatz (Satz 2.5) angegeben.

Mohammad Al-Turkistany
quelle