Um über Dinge wie die NP-Vollständigkeit nachzudenken, verwenden wir normalerweise Mehrfachreduktionen (dh Karp-Reduktionen). Dies führt zu Bildern wie diesen:
(unter Standardvermutungen). Ich bin sicher, wir sind alle mit solchen Dingen vertraut.
Welches Bild bekommen wir, wenn wir mit Turing-Reduktionen (dh Cook-Reduktionen) arbeiten? Wie verändert sich das Bild?
Was sind insbesondere die wichtigsten Komplexitätsklassen und in welcher Beziehung stehen sie zueinander? Ich vermute, dass die Rolle spielt, die früher von und (weil unter Turing-Reduktionen genauso geschlossen ist wie unter Karp-Reduktionen); ist das ungefähr richtig? N P c o N P P N P N P
Sollte das Bild also jetzt wie aussehen , dh wie folgt?
Gibt es eine neue Sequenz, die eine Rolle spielt, die der Polynomhierarchie entspricht? Gibt es eine natürliche Folge von Komplexitätsklassen , ,, ..., so dass jede Komplexitätsklasse unter Turing-Reduktionen geschlossen wird? Was ist die "Grenze" dieser Sequenz: es ? Wird erwartet, dass sich jede Klasse in der Sequenz von der vorherigen unterscheidet? (Mit "erwartet" meine ich unter plausiblen Vermutungen, ähnlich dem Sinne, in dem erwartet wird, dass .)C 1 = P N P C 2 = & dgr; P H P ≠ N P.
Verwandte: Viele-Eins-Reduktionen vs. Turing-Reduktionen, um NPC zu definieren . In diesem Artikel wird erklärt, dass wir mit Karp-Reduktionen arbeiten, weil wir dadurch eine feinkörnigere, reichhaltigere und präzisere Hierarchie erhalten. Im Wesentlichen frage ich mich, wie die Hierarchie aussehen würde, wenn wir mit Turing-Reduktionen arbeiten würden: Wie die gröbere, weniger reiche, weniger präzise Hierarchie aussehen würde.
Antworten:
Sie können . Einige Autoren bezeichnen sie mit (ähnlich den und ). Es ist im Wesentlichen der Turing-Abschluss der Polynomhierarchie. Wir haben Daher . ◻ P i Δ P i ∇ P i P Σ P i ⊆ N P Σ P i = Σ P i + 1 ⊆ P Σ P i + 1 P P H = ∑ i ≥ 0 P Σ P i = ∑ i ≥ 0 Σ P i = P H.PΣPi □Pi ΔPi ∇Pi
Wenn die Polynomhierarchie nicht zusammenbricht, sind alle Einschlüsse streng.
quelle