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

14

Des langues telles que sont RE-complètes sous plusieurs réductions. Il est trivial de voir que co-RE a aussi des problèmes complets. S. Schmitz [1] considère certaines classes entre ELEM et REC . Ils présentent des problèmes complets pour ces classes dans le cadre de réductions spécialement conçues.HALTTMRE-completeco-REELEMREC

Existe-t-il des problèmes complets pour (aka REC ) 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)?R=REco-REREC


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

mdxn
la source
1
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
3
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
1
@YuvalFilmus: Oui, je le suis.
mdxn
1
@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
mdxn

Réponses:

8

R

Voici l'argument:

Supposons qu'il existe un problème complet ARRARR

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

Kaveh
la source
1
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 ennk+k FO (LFP, BIT) .
Kaveh