Existe-t-il un problème complet pour la classe des problèmes décidables de Turing?

Des langues telles que sont sous plusieurs réductions. Il est trivial de voir que a aussi des problèmes complets. S. Schmitz [1] considère certaines classes entre et . Ils présentent des problèmes complets pour ces classes dans le cadre de réductions spécialement conçues. $\text{HALT}_{TM}$ $\textsf{RE-complete}$ $\text{co-RE}$ $\text{ELEM}$ $\text{REC}$

Existe-t-il des problèmes complets pour (aka ) par rapport à des réductions plus faibles? Les réductions de Turing sont inappropriées car elles sont capables de faire tout le travail. Faut-il s'attendre à ce que de telles réductions soient artificielles ou non ( par exemple, plusieurs réductions qui sont limitées à la récursion primitive)? $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ $\textsf{REC}$

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

computability reductions turing-completeness recursion-theory mdxn
la source

Cette question semble un peu simple, mais un professeur et moi l'avons effacée. Je ne serais pas surpris si la réponse était évidente. Mes excuses si c'est le cas. Néanmoins, ce sera bien d'avoir la réponse quelque part sur Internet.

mdxn

Tous les problèmes récursifs non triviaux sont complétés par des réductions récursives à plusieurs. Recherchez-vous des réductions plus faibles?

Yuval Filmus

@YuvalFilmus: Oui, je le suis.

mdxn

@YuvalFilmus Je fournirai un peu plus d'informations. Prenons le cas avec

. Lorsque nous examinons l'exhaustivité de P, nous avons tendance à considérer des réductions plus faibles telles que l'espace de journal ou les réductions de premier ordre. Si nous avons défini la complétude P en utilisant des réductions polynomiales à plusieurs, alors nous rencontrons une situation similaire que vous évoquez (une réduction FO est connue pour être strictement plus faible). Nous pouvons faire en sorte que la réduction effectue presque tout le calcul au lieu d'identifier les problèmes complets de manière fructueuse.

P

$\textsf{P}$

mdxn

$\mathsf{R}$

Voici l'argument:

Supposons qu'il existe un problème complet $A$ $\mathsf{R}$ $\mathsf{R}$ $A$ $\mathsf{R}$ $\mathsf{R}$

Dans la littérature, recherchez l'ensemble des fonctions récursives / calculables totales .

Kaveh
la source

Bienvenue à nouveau, Kaveh! C'est bon de te revoir!

David Richerby

Pourquoi les réductions de temps poly sont-elles énumérables?

Ariel

Oui, vous l'avez mentionné dans le post :) mais je suis un peu confus, pouvez-vous élaborer sur l'énumération?

Ariel

@Ariel, énumère les machines de Turing avec des horloges de la forme

. Il existe d'autres moyens plus intéressants (mais plus difficiles à prouver) de les énumérer, par exemple les fonctions polynomiales calculables en temps sont exactement des requêtes qui peuvent être exprimées en

n^{k} + k

$n^k+k$ FO (LFP, BIT) .

Kaveh

Existe-t-il un problème complet pour la classe des problèmes décidables de Turing?

Réponses: