Existe um problema completo para a classe de problemas decidíveis de Turing?

14

Linguagens como são sob muitas one-redução. É trivial ver que tem problemas completos. S. Schmitz [1] considera algumas classes entre e . Eles apresentam problemas completos para essas classes sob reduções especificamente criadas.HALTTM co-RERE-completeco-REELEMREC

Existem problemas completos para (aka ) em relação a reduções mais fracas? Reduções de Turing são inadequadas porque são capazes de fazer todo o trabalho. Deveríamos esperar que essas reduções fossem inventadas ou não ( por exemplo, muitas reduções restritas à recursão primitiva)?RECR=REco-REREC


[1] Hierarquias da complexidade de Sylvain Schmitz além do ensino fundamental 2013 http://arxiv.org/abs/1312.5686

mdxn
fonte
1
Essa pergunta parece um pouco simples, mas um professor e eu a deixamos em branco. Eu não ficaria surpreso se a resposta fosse óbvia. Peço desculpas se este for o caso. Mesmo assim, será bom ter a resposta em algum lugar da internet.
Mdxn
3
Todo problema recursivo não trivial é concluído sob reduções recursivas de muitos. Você está procurando reduções mais fracas?
Yuval Filmus
1
@YuvalFilmus: Sim, eu sou.
Mdxn
1
@YuvalFilmus fornecerei mais informações. Consideremos o caso com . Ao analisar a completude P, tendemos a considerar reduções mais fracas, como espaço de log ou reduções de primeira ordem. Se definimos a completude-P usando reduções polinomiais de muitos-um, então nos deparamos com uma situação semelhante à sua (uma redução de FO é conhecida por ser estritamente mais fraca). Podemos fazer com que a redução execute quase todo o cálculo, em vez de identificar problemas completos de maneira proveitosa. P
Mdxn

Respostas:

8

Geralmente, uma classe com um problema completo em uma boa classe de reduções implica que a classe pode ser enumerada. não é computávelmente enumerável; portanto, ele não possui um problema completo com relação a uma boa classe de reduções.R

Aqui está o argumento:

Suponha que há um problema completa para R . Portanto, para qualquer problema em R pode ser obtido a partir de uma redução (digamos tempo polinomial muitos-um reduções) combinado com um . Podemos enumerar as reduções computacionalmente; portanto, enumerar R computavelmente . Mas R não é computávelmente enumerável (caso contrário, poderíamos diagonalizar).ARRARR

Na literatura, procure o conjunto de funções recursivas / computáveis ​​totais .

Kaveh
fonte
1
Bem-vindo de volta, Kaveh! Bom te ver de novo!
David Richerby
Por que as reduções de tempo poli são enumeráveis?
Ariel
Sim, você mencionou no post :) no entanto, estou meio confuso, você pode elaborar a enumeração?
Ariel
nk+k