¿Existe un problema completo para la clase de problemas decidibles de Turing?

Idiomas como $\text{HALT}_{TM}$ son $\textsf{RE-complete}$ bajo muchas reducciones. Es trivial ver que $\text{co-RE}$ tiene problemas completos. S. Schmitz [1] considera algunas clases entre $\text{ELEM}$ y $\text{REC}$ . Presentan problemas completos para estas clases bajo reducciones específicamente diseñadas.

¿Existen problemas completos para $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (también conocido como $\textsf{REC}$ ) en relación con reducciones más débiles? Las reducciones de Turing son inapropiadas porque son capaces de hacer todo el trabajo. ¿Deberíamos esperar que tales reducciones sean artificiales o no ( por ejemplo , reducciones de muchos que están restringidas a la recursividad primitiva)?

[1] Sylvain Schmitz Complex Jierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686

computability reductions turing-completeness recursion-theory mdxn
fuente

Esta pregunta parece un poco simple, pero un profesor y yo la ignoramos. No me sorprendería si la respuesta es obvia. Mis disculpas si este es el caso. Aun así, será bueno tener la respuesta en algún lugar de Internet.

mdxn

Todo problema recursivo no trivial se completa con reducciones recursivas de muchos. ¿Estás buscando reducciones más débiles?

Yuval Filmus

@YuvalFilmus: Sí, lo estoy.

mdxn

@YuvalFilmus Proporcionaré un poco más de información. Considere el caso de

. Cuando observamos la integridad de P, tendemos a considerar reducciones más débiles, como el espacio logs o las reducciones de primer orden. Si definimos la integridad de P utilizando reducciones polinómicas de muchos-uno, entonces nos encontramos con una situación similar a la que usted plantea (se sabe que una reducción de FO es estrictamente más débil). Podemos hacer que la reducción realice casi todos los cálculos en lugar de identificar problemas completos de manera fructífera.

P

$\textsf{P}$

mdxn

Respuestas:

Generalmente, una clase que tiene un problema completo bajo una buena clase de reducciones implica que la clase puede ser enumerada. $\mathsf{R}$ no es computablemente enumerable, por lo tanto, no tiene un problema completo con respecto a una buena clase de reducciones.

Aquí está el argumento:

Supongamos que hay un problema completo de . Por lo tanto, para cualquier problema en se puede obtener de una reducción (digamos tiempo polinómico many-uno reducciones) en combinación con . Podemos enumerar de manera computacional las reducciones, por lo tanto, podemos enumerar computacional . Pero $A$ $\mathsf{R}$ $\mathsf{R}$ $A$ $\mathsf{R}$ $\mathsf{R}$ no es computablemente enumerable (de lo contrario podríamos diagonalizar).

En la literatura, busque el conjunto de funciones recursivas / computables totales .

Kaveh
fuente

Bienvenido de nuevo, Kaveh! ¡Qué bueno verte de nuevo!

David Richerby

¿Por qué son enumerables las reducciones de tiempo poli?

Ariel

Sí, lo mencionaste en la publicación :) Sin embargo, estoy un poco confundido, ¿puedes explicar la enumeración?

Ariel

@Ariel, enumera las máquinas de Turing con relojes de la forma

. Hay otras formas más interesantes (pero más difíciles de probar) de enumerarlas, por ejemplo, las funciones computables de tiempo polinómico son consultas exactas que se pueden expresar en FO (LFP, BIT) .

n^{k} + k

$n^k+k$

Kaveh