¿Variantes NP-completas de problemas indecidibles?

Ejemplos de variantes completas de limitadas de conjuntos indecidibles:$NP$

Problema de detención delimitado = { | La máquina NTM detiene y acepta en pasos}M x $(M, x, 1^t)$$M$$x$$t$

Mosaico limitado = { | hay un mosaico de un cuadrado de área por mosaicos de }t 2$(T, 1^t)$$t^2$$T$

Problema de correspondencia posterior limitado = { | hay un conjunto de fichas de dominó que utiliza como máximo fichas de dominó de un conjunto de fichas de dominó (incluidas fichas de dominó repetidas)}k $(T, 1^t)$$k$$T$

¿Es siempre posible obtener una variante completa de de cada problema indecidible imponiendo algunos límites en el cálculo? ¿Hay otros ejemplos naturales de este tipo?$NP$

Como señaló Jukka, la respuesta es trivialmente negativa para todos los problemas indecidibles.

Una pregunta más razonable sería: ¿Puede cada problema completo para la clase de lenguajes recursivamente enumerables hacerse completo NP de una manera directa? No estoy seguro de que esto sea cierto en general, pero en los casos especiales que menciona en su pregunta (Bounded-Halting and Tiling) estos problemas están completos para RE incluso bajo reducciones de tiempo polinomiales "especiales". (Dejo "especial" en su mayoría indefinido en esta respuesta, pero las propiedades necesarias se pueden resolver a partir de él).

Entonces, si formulamos una pregunta aún más razonable: ¿puede cada problema que se complete (bajo reducciones especiales de tiempo múltiple) para la clase de lenguajes recursivamente enumerables hacerse NP-completo de una manera directa? Aquí la respuesta es sí . Tome cualquier problema RE-completo , definido con respecto a una máquina Turing que toma un par de entradas , de modo que . Estamos asumiendo que hay una transformación polinómica del problema de la parada a . Defina "Bounded-A" como el conjunto de pares modo que haya una de longitud como máximoM $A$$M_A$x ∈ $(x,y)$A ( x , 1 t ) y t M A ( x , y ) $x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$$A$$(x,1^t)$$y$$t$tal que detiene en pasos.$M_A(x,y)$$t$

Claramente "Bounded-A" está en . Es también -Complete porque podemos reducir el -Complete acotada Detener Problema a Limitado-A en tiempo polinómico (Tenga en cuenta que aquí se necesita propiedades especiales en el polinomio de reducción del tiempo de para asegurar que se traslada a Limitado-Detener así: es decir, debe poder calcular eficientemente un límite superior sobre cuánto tiempo debe , suponiendo que detenga en pasos).$NP$$NP$$NP$$R$$t'$$M_A(R(M,x),y)$$M(x)$$t$

Ahora, ¿hay un lenguaje que se RE-complete bajo (digamos) reducciones de tiempo doblemente exponencial pero no bajo reducciones de tiempo exponencial? Para tal problema, es poco probable que pueda modificarlo trivialmente para obtener una versión completa de . Supongo que tal problema puede construirse artificialmente.$NP$

Creo que esto se puede hacer para problemas con cierto grado específico de insolubilidad . Para citar de Wikipedia: "Cada grado de Turing es infinitamente contable, es decir, contiene exactamente conjuntos ".$\aleph_0$

Entonces, supongo, para cada problema dentro del mismo grado de insolvencia, hay algún tipo de recurso (tiempo) limitado, que proporciona un lenguaje NP-completo.

Observación: Tal vez debería haber sido más conservador al decir "para cada problema dentro del mismo grado de insolubilidad". Es posible que la afirmación anterior solo sea cierta para la clase de problemas que poseen el mismo grado que, por ejemplo, el problema HALTING.

Ver también: Martin Davis, ¿Qué es ... Turing Reducibility ?, Avisos de la AMS, 53 (10), pp. 1218-1219, 2006.