Referenz für Turing zu vielen Reduzierungen

Ich suche nach einer Referenz zum "Reduzieren" von Turing-Reduzierungen auf Mehrfachreduzierungen. Ich denke an eine Aussage der folgenden Form (ähnlich genug Aussagen würden mich auch befriedigen):

Satz. Wenn , dann . $\mathsf{A}\leq_T^f \mathsf{B}$ $\mathsf A\leq_m^{2^f}\mathsf B^{tt}$

wobei " " und " " jeweils und Vielfachverringerungen der deterministischen Zeit bezeichnen und " " eine "Wahrheitstabellen" -Variante von bezeichnet die Sprache , die eine boolesche Kombination von Prüfungen " " . $\leq_T^f$ $\leq_m^f$ $f(n)$ $\mathsf{B}^{tt}$ $\mathsf{B}$ $x\in\mathsf{B}$

Beweisidee für die Aussage: Simulieren Sie die -zeitbegrenzte Orakel-Turing-Maschine, die bei der Turing-Reduktion verwendet wird: Es ist einfach genug, auch in der Zeit einen nicht deterministischen Turing-Wandler zu erhalten , der die Antworten des Orakels errät und schreibt eine Konjunktion von Prüfungen " " oder " " in die Ausgabe, die von einer -Maschine ausgewertet werden sollen . Dieser Wandler kann bestimmt werden, indem beide Ergebnisse der Orakelrufe untersucht und durch Disjunktionen in der Ausgabe behandelt werden. es funktioniert jetzt in der Zeit . $f(n)$ $f(n)$ $\mathsf B$ $x\in\mathsf B$ $x\not\in\mathsf{B}$ $\mathsf B^{tt}$ $2^{f(n)}$

Seltsamerweise kann ich in komplexen Lehrbüchern kein verwandtes Ergebnis finden.

Bearbeiten: Umbenennung von " " in " ", um die Beziehung zu Wahrheitstabellen hervorzuheben, wie von @ MarkusBläser hervorgehoben. $A\mathsf B$ $\mathsf B^{tt}$

cc.complexity-theory reference-request complexity-classes Sylvain
quelle

Interessant. Anders ausgedrückt, Sie reduzieren es zunächst auf das Problem der Überprüfung, ob eine Berechnung der Länge der Reduktionsmaschine mit Orakel akzeptiert, und reduzieren diese dann auf indem Sie alle akzeptierenden Zweige berücksichtigen (unter Berücksichtigung aller möglichen Werte) der Mitgliedschaft in Abfragen) und in einer einzigen Abfrage an fragen, ob eine von ihnen korrekt ist. Der naheliegende Ort, an dem dies überprüft werden muss, ist die klassische Rekursionstheorie. Sie behandelt verschiedene Reduktionen und ihre Beziehungen ausführlich, aber ich kann mich nicht erinnern, etwas Ähnliches gesehen zu haben.

f (| x |)

$f(|x|)$

B

$B$

A B

$AB$

B

$B$

A B

$AB$

Kaveh

Was ist der Unterschied zu einer Reduzierung der Wahrheitstabelle?

Markus Bläser

@ MarkusBläser: Nicht viel, die Viel-Eins-Reduktion könnte (glaube ich) auch als Wahrheitstabellenreduktion . Irgendwelche Referenzen für diese Variante des Satzes?

A \leq_{m}^{2^{f}} A B

$\mathsf A\leq^{2^f}_mA\mathsf B$

A \leq_{t t}^{2^{f}} B

$\mathsf A\leq_{tt}^{2^f}\mathsf B$

Sylvain

ps: Wenn Sie hier keine Antwort erhalten, möchten Sie diese möglicherweise auf MO erneut veröffentlichen. Es gibt eine Reihe von Berechenbarkeitstheoretikern auf MO, die cstheory nicht besuchen (zumindest nicht sehr oft).

Kaveh

@ Sylvain Super Frage.

Tayfun Pay

Referenz für Turing zu vielen Reduzierungen

Antworten: