Des variantes NP-complètes de problèmes indécidables?

10

Exemples de variantes bornées d'ensembles indécidables: $NP$

Problème d'arrêt limité = { | La machine NTM arrête et accepte dans les étapes } $(M, x, 1^t)$ $M$ $x$ $t$

Mosaïque délimitée = { | il y a un carrelage d'un carré de zone par des tuiles de } $(T, 1^t)$ $t^2$ $T$

Problème de correspondance de poste borné = { | il existe un ensemble de dominos correspondant qui utilise au plus dominos d'un ensemble de dominos (y compris les dominos répétés)} $(T, 1^t)$ $k$ $T$

Est-il toujours possible d'obtenir une variante complète de de chaque problème indécidable en imposant des limites au calcul? Existe-t-il d'autres exemples naturels de ce genre? $NP$

cc.complexity-theory np-hardness Mohammad Al-Turkistany
la source

4

Il existe un nombre incalculable de problèmes indécidables, mais seulement de nombreux problèmes NP-complets.

Jukka Suomela

13

Comme l'a souligné Jukka, la réponse est trivialement non pour tous les problèmes indécidables.

Une question plus raisonnable serait: Est-ce que chaque problème qui est complet pour la classe des langages récursivement énumérables peut être rendu NP-complet d'une manière simple? Je ne suis pas sûr que ce soit vrai en général, mais dans les cas spéciaux que vous mentionnez dans votre question (Bounded-Halting et Tiling), ces problèmes sont complets pour RE même sous des réductions de temps polynomiales "spéciales". (Je laisse "spécial" la plupart du temps indéfini dans cette réponse, mais les propriétés nécessaires peuvent être déterminées à partir de cela.)

$A$ $M_A$ $(x,y)$ $x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$ $A$ $(x,1^t)$ $y$ $t$ $M_A(x,y)$ $t$

$NP$ $NP$ $NP$ $R$ $t'$ $M_A(R(M,x),y)$ $M(x)$ $t$

$NP$

Ryan Williams
la source

1

$\aleph_0$

Ensuite, je suppose que pour chaque problème dans le même degré d'insolvabilité, il existe un certain type de ressource (temporelle), qui donne un langage NP-complet.

Remarque: j'aurais peut-être dû être plus prudent en disant "pour chaque problème dans le même degré d'insolvabilité". Il se peut que l'énoncé ci-dessus ne soit vrai que pour la classe de problèmes possédant le même degré que, disons, le problème HALTING.

Voir aussi: Martin Davis, What Is ... Turing Reducibility?, Notices of the AMS, 53 (10), pp. 1218-1219, 2006.

MS Dousti
la source

Je suppose que votre idée ne fonctionne que pour les degrés de Turing polynomiaux (c'est-à-dire que deux langues sont au même degré si elles sont Turing polytemporelles réductibles l'une à l'autre).

Joshua Grochow

@Joshua: Merci. Je pense que tu as raison. Donc, la réponse doit être modifiée comme suit: Tout problème indécidable, qui a le même degré de Turing polynomial-time que HALTING PROBLEM, peut être converti en un problème NP en mettant une limite sur ses ressources (comme décrit par l'OP).

MS Dousti

Des variantes NP-complètes de problèmes indécidables?

Réponses: