Referencia para Turing a reducciones de muchos

Estoy buscando una referencia sobre 'reducir' las reducciones de Turing a muchas reducciones. Tengo en mente una declaración de la siguiente forma (declaraciones suficientemente similares también me satisfarían):

Teorema. Si , entonces . $\mathsf{A}\leq_T^f \mathsf{B}$ $\mathsf A\leq_m^{2^f}\mathsf B^{tt}$

donde " " y " " denotan respectivamente las reducciones de Turing y de muchos en el tiempo determinista , y " " denota una variante de la "tabla de verdad" el idioma , que evalúa una combinación booleana de controles " ". $\leq_T^f$ $\leq_m^f$ $f(n)$ $\mathsf{B}^{tt}$ $\mathsf{B}$ $x\in\mathsf{B}$

Idea de prueba para el enunciado: simule la máquina de Turing del oráculo delimitada por el tiempo utilizada en la reducción de Turing: es bastante fácil obtener un transductor de Turing no determinista también en el tiempo que adivina las respuestas del oráculo y escribe una conjunción de cheques " " o " " en la salida, para ser evaluados por una máquina . Este transductor se puede determinar explorando ambos resultados de las llamadas al oráculo y manejándolos mediante disyunciones en la salida; ahora funciona en el tiempo . $f(n)$ $f(n)$ $\mathsf B$ $x\in\mathsf B$ $x\not\in\mathsf{B}$ $\mathsf B^{tt}$ $2^{f(n)}$

Por extraño que parezca, no puedo encontrar ningún resultado relacionado en los libros de texto de complejidad.

Editar: renombrado " " en " " para enfatizar la relación con las tablas de verdad, como lo señaló @ MarkusBläser. $A\mathsf B$ $\mathsf B^{tt}$

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

Interesante. Para decirlo de otra manera, primero lo reduce al problema de verificar si cualquier cálculo de longitud

de la máquina de reducción con oráculo

acepta, y luego reduce eso a

considerando todas las ramas de aceptación (considerando todas las posibles valores de membresía en consultas

) y preguntar en una sola consulta a

si alguna de ellas es correcta. El lugar obvio para verificar es la Teoría de la recursión clásica, discute varias reducciones y sus relaciones ampliamente, pero no recuerdo haber visto nada similar.

f (| x |)

$f(|x|)$

B

$B$

A B

$AB$

B

$B$

A B

$AB$

Kaveh

¿Cuál es la diferencia con una reducción de la tabla de verdad?

Markus Bläser

@ MarkusBläser: No mucho, los muchos-uno reducción

podría (creo) también ser visto como una reducción tabla de verdad

. ¿Alguna referencia para esta variante del teorema?

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: si no obtiene una respuesta aquí, es posible que desee volver a publicar esto en MO, hay una serie de teóricos de computabilidad en MO que no visitan cstheory (al menos no muy a menudo).

Kaveh

@Sylvain Awesome Question.

Tayfun Pay

Referencia para Turing a reducciones de muchos

Respuestas: