Variantes NP-completas de problemas indecidíveis?

Exemplos de variantes limitadas de completas de conjuntos indecidíveis:$NP$

Problema de parada limitada = { | A máquina NTM interrompe e aceita dentro de etapas}$(M, x, 1^t)$$M$$x$$t$

Lado a lado com limite = { | há um quadrado de um quadrado da área por ladrilhos de }$(T, 1^t)$$t^2$$T$

Problema de correspondência pós-limitada = { | existe um conjunto correspondente de dominós que usa no máximo dominós de um conjunto de dominós (incluindo dominós repetidos)}$(T, 1^t)$$k$$T$

É sempre possível obter -completo variante de todos os problemas Indecidíveis impondo alguns limites sobre o cálculo? Existem outros exemplos naturais desse tipo?$NP$

Como Jukka apontou, a resposta é trivialmente não para todos os problemas indecidíveis.

Uma pergunta mais razoável seria: todo problema que é completo para a classe de linguagens recursivamente enumeráveis ​​pode ser feito NP-completo de maneira direta? Não tenho certeza de que isso seja verdade em geral, mas nos casos especiais mencionados na sua pergunta (Interrupção limitada e lado a lado), esses problemas estão completos para o ER, mesmo sob reduções polinomiais "especiais". (Deixo "especial" principalmente indefinido nesta resposta, mas as propriedades necessárias podem ser trabalhadas a partir dela.)

Portanto, se fizermos uma pergunta ainda mais razoável: todo problema que está completo (com reduções especiais de politímo) para a classe de linguagens recursivamente enumeráveis ​​pode ser feito NP-completo de maneira direta? , aqui a resposta é sim . Tome qualquer problema RE-completo , definido em relação a uma máquina de Turing M A que aceite um par de entradas ( x , y ) , de modo que x ∈ $A$$M_A$$(x,y)$ . Estamos assumindo que há uma redução de tempo polinomial do Deter Problema para A . Defina "Limite-A" como o conjunto de pares ( x , 1 t ), de modo que exista um y de comprimento no máximo t, de modo que M A ( x , y ) pare dentro de t etapas.$x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$$A$$(x,1^t)$$y$$t$$M_A(x,y)$$t$

Claramente "delimitada-A" é em . É também N P -completo porque podemos reduzir o N P -completo Bounded Travar Problema para Bounded-A em tempo polinomial (Note que aqui você precisa propriedades especiais sobre o polinômio redução do tempo de R para garantir que ele transporta para Bounded-Deter como bem: ou seja, você precisa ser capaz de calcular com eficiência um limite superior t ' em quanto tempo M A ( R ( M , x ) , y ) precisa ser executado, assumindo que M ( x ) pare dentro$NP$$NP$$NP$$R$$t'$$M_A(R(M,x),y)$$M(x)$ passos.)$t$

Agora, existe um idioma que é RE-completo sob (digamos) reduções no tempo duplamente exponencial, mas não sob reduções no tempo exponencial? Para tal problema um, é improvável que você pode trivialmente modificá-lo para obter uma versão -completo. Eu acho que esse problema pode ser artificialmente construído.$NP$

Eu acho que isso pode ser feito para problemas com algum grau especificado de insolubilidade . Para citar Wikipedia: "Cada Turing grau é infinito contável, ou seja, ele contém exatamente sets."$\aleph_0$

Então, eu acho que, para cada problema com o mesmo grau de insolubilidade, existe algum tipo de recurso (tempo) vinculado, o que fornece uma linguagem NP-completa.

Observação: Talvez eu devesse ter sido mais conservador ao dizer "para cada problema dentro do mesmo grau de insolubilidade". Pode ser que a afirmação acima seja verdadeira apenas para a classe de problemas que possuem o mesmo grau que, digamos, do problema HALTING.

Os dados foram analisados ​​por meio de entrevistas semiestruturadas e entrevistas semi-estruturadas com os participantes.