Welche NP-Entscheidungsprobleme sind nicht selbstreduzierbar?

8

Also haben wir gerade im Unterricht etwas über Selbstreduzierbarkeit gelernt. Mein Professor und unser Lehrbuch würden sich nicht dazu verpflichten zu sagen, dass alle Probleme in NP selbstreduzierbar sind, aber es schien keine Beispiele für Probleme zu geben, die dies nicht sind. Ich habe mich gefragt, ob es Beispiele gibt oder ob es nur eine Situation ist, in der man nicht einfach ein Negativ beweisen kann. Wikipedia sagt nurIt is conjectured that the integer factorization problem is not self-reducible.

Googeln fand ein Ergebnis , das besagt, dass die Färbung des planaren Graphen 4 nicht selbstreduzierbar ist, da sich die LF-k-Färbung für einen planaren Graphen auf diese Reduktion reduziert, aber ich konnte dem Beweis im Moment nicht ganz folgen.

Ist dies ein aktuelles Beispiel für einen Selbstreduzierbarkeitsnachweis, und gibt es andere?

complexity-theory reductions decision-problem np Adam Martin
quelle
@ DW Nein, nur Selbstreduzierbarkeit. Lies das Dokument.
Yuval Filmus

Antworten:

3

Das Papier zeigt in der Tat, dass die Färbung des planaren Graphen vier im Sinne von Schnorr nicht selbstreduzierbar ist. Es gibt mehrere andere Sinne, unter denen jedes Problem in P selbstreduzierbar ist. Siehe das Folgepapier von Große, Rothe und Wechsung . Mir ist kein anderes Ergebnis dieser Art bekannt. Wenn Sie alle Artikel durchgehen, in denen der von Ihnen erwähnte Artikel zitiert wird (dies kann beispielsweise mit Google Scholar erfolgen), gibt es keine derartigen Probleme.

Yuval Filmus
quelle
Vielen Dank! Kurze Frage: War mein Verständnis des Hauptteils ihres Beweises korrekt oder habe ich ihn nicht richtig befolgt? Wir haben nicht viel mit tatsächlichen formalen Sprachdefinitionen gemacht, wir waren etwas abstrakter, daher ist es schwierig, sich in dieser Detailstufe sicher zu fühlen. (Ich werde auch nur ein bisschen warten, um die Antwort zu akzeptieren, da ich nur minimale Fachkenntnisse habe und abwarten möchte, ob andere mitmachen.)
Adam Martin
Wenn ein Problem im Sinne von Schnorr selbstreduzierbar ist und die Entscheidungsversion in Polynomzeit gelöst werden kann, finden Sie die lexikographisch erste Lösung in Polynomzeit. Dies beruht auf der besonderen Definition von Schnorr. In diesem Fall ist die Entscheidungsversion sehr einfach (die Antwort lautet immer JA), während die Lex-First-Version NP-schwer ist, sodass das Problem nicht selbstreduzierbar ist, es sei denn, P = NP.
Yuval Filmus
Vielen Dank! Ich denke, der einzige Stolperstein, den ich noch habe, sind die unterschiedlichen Sinne der Selbstreduzierbarkeit. Sollte ich eine andere Frage stellen oder ist es eine geringfügige Unterscheidung, die ich hier stellen / mein Original bearbeiten kann? Wir haben allgemein gelernt, dass ein Problem selbstreduzierbar ist, wenn Sie bei einer Polytime-Existenzlösung eine Polytime-Suchlösung erstellen können. Gibt es hier eine technische Unterscheidung, von der dieses Ergebnis abhängt?
Adam Martin
1
Schauen Sie sich das Papier von Große et al. An, in dem dieser Punkt diskutiert wird.
Yuval Filmus