Gibt es ein vollständiges Problem für die Klasse der entscheidbaren Probleme?

14

Sprachen wie sind mit vielen Reduzierungen. Es ist trivial zu sehen, dass auch vollständige Probleme hat. S. Schmitz [1] betrachtet einige Klassen zwischen und . Sie stellen für diese Klassen vollständige Probleme unter speziell gestalteten Reduzierungen.HALTTMRE-completeco-REELEMREC

Gibt es vollständige Probleme für (auch bekannt als ) im Vergleich zu schwächeren Reduktionen? Turing-Reduktionen sind ungeeignet, weil sie die ganze Arbeit erledigen können. Sollten wir damit rechnen, dass solche Reduktionen erfunden werden, oder nicht ( z. B. viele Reduktionen, die auf die primitive Rekursion beschränkt sind)?R=REco-REREC


[1] Sylvain Schmitz Komplexitätshierarchien jenseits der Grundstufe 2013 http://arxiv.org/abs/1312.5686

mdxn
quelle
1
Diese Frage scheint ein bisschen einfach zu sein, aber ein Professor und ich haben sie ausgeblendet. Es würde mich nicht wundern, wenn die Antwort offensichtlich ist. Ich entschuldige mich, wenn dies der Fall ist. Trotzdem wird es schön sein, die Antwort irgendwo im Internet zu haben.
mdxn
3
Jedes nicht-triviale rekursive Problem ist unter rekursiven Vielfachreduktionen abgeschlossen. Suchen Sie nach schwächeren Ermäßigungen?
Yuval Filmus
1
@YuvalFilmus: Ja, das bin ich.
Mdxn
1
@YuvalFilmus Ich gebe ein bisschen mehr Infos. Betrachten wir den Fall mit . Bei der Betrachtung der P-Vollständigkeit neigen wir dazu, schwächere Verringerungen zu berücksichtigen, wie z. B. Verringerungen des logspace oder Verringerungen erster Ordnung. Wenn wir die P-Vollständigkeit mit polynomiellen Viel-Eins-Reduktionen definiert haben, stoßen wir auf eine ähnliche Situation, die Sie ansprechen (eine FO-Reduktion ist bekanntermaßen strikt schwächer). Wir können die Reduktion veranlassen, fast die gesamte Berechnung durchzuführen, anstatt vollständige Probleme auf fruchtbare Weise zu identifizieren. P
mdxn

Antworten:

8

Im Allgemeinen impliziert eine Klasse mit einem vollständigen Problem unter einer netten Klasse von Reduktionen, dass die Klasse aufgezählt werden kann. ist nicht berechenbar aufzählbar, daher hat es kein vollständiges Problem bezüglich einer schönen Klasse von Reduktionen.R

Hier ist das Argument:

Angenommen, es gibt ein vollständiges Problem ist für R . Daher kann für jedes Problem in R aus einer Reduktion (sagen wir Polynom-Zeit-Vielfachreduktionen) in Kombination mit A erhalten werden . Wir können die Reduktionen rechnerisch aufzählen, daher können wir R rechnerisch aufzählen . Aber R ist nicht berechenbar aufzählbar (sonst könnten wir diagonalisieren).ARRARR

Suchen Sie in der Literatur nach der Menge der gesamten rekursiven / berechenbaren Funktionen .

Kaveh
quelle
1
Willkommen zurück, Kaveh! Schön dich wieder zu sehen!
David Richerby
Warum sind Poly Time Reductions aufzählbar?
Ariel
Ja, du hast es in der Post erwähnt.
Ariel
nk+k