Pourquoi NP est-il dans EXPTIME?

Existe-t-il un moyen simple de comprendre pourquoi NP est dans EXPTIME? Il me semble a priori concevable qu'il pourrait y avoir un problème qui nécessite un temps super-exponentiel à résoudre, mais dont la solution pourrait être vérifiée en temps polynomial.

complexity-theory complexity-classes tparker
la source

En fait, NP PSPACE.

\subseteq

$\subseteq$

Bienvenue en informatique! Qu'as-tu essayé? Où êtes-vous resté coincé? Nous ne voulons pas simplement faire votre travail (à domicile) pour vous; nous voulons que vous gagniez en compréhension. Cependant, comme nous ne savons pas quel est votre problème sous-jacent, nous ne pouvons donc pas commencer à vous aider. Voir ici pour une discussion pertinente. Si vous ne savez pas comment améliorer votre question, pourquoi ne pas demander autour de Computer Science Chat ? Vous pouvez également consulter nos questions de référence .

Raphael

Tout problème dans NP se trouve dans EXPTIME car vous pouvez utiliser le temps exponentiel pour essayer tous les certificats possibles ou pour énumérer tous les chemins de calcul possibles d'une machine non déterministe.

Plus formellement, il existe deux définitions principales de NP . L'une est qu'un langage est en NP ssi il y a une relation telle que $L$ $R$

il existe un polynôme tel que, pour tout , , $p$ $(x,y)\in R$ $|y|\leq p(|x|)$
étant donné la chaîne , nous pouvons déterminer dans le polynôme temporel danssi , et $x\#y$ $|x\#y|$ $(x,y)\in R$
$L = \{x\mid (x,y)\in R\}$ .

Donc, si nous avons un temps exponentiel et que nous voulons savoir si , nous pouvons simplement essayer toutes les valeurs possibles pour ~ et voir si pour l'un d'eux. Cela prend du temps , donc EXPTIME . $x\in L$ $|\Sigma|^{p(n)}$ $y$ $(x,y)\in R$ $2^{O(p(n))}$ $L\in\,$

Alternativement, nous pouvons définir NP comme l'ensemble des langages décidés par les machines de Turing non déterministes à temps polynomial. Dans ce cas, supposons que soit décidé par la machine dans le temps pour un polynôme , pour des entrées de longueur . Ensuite fait au plus choix non déterministes tout en déterminant si . En examinant la fonction de transition de , nous pouvons trouver une constante telle que a au plus choix non déterministes à chaque étape du calcul (indépendamment de l'entrée), donc elle a au plus $L$ $M$ $p(n)$ $p$ $n$ $M$ $p(|x|)$ $x\in L$ $M$ $k$ $M$ $k$ $k^{p(|x|)} = 2^{O(p(|x|))}$ différentes séquences de choix non déterministes lors de la lecture de l'entrée . Compte tenu du temps exponentiel, nous pouvons simuler chacune de ces possibilités l'une après l'autre et voir si l'une d'entre elles accepte. $x$

David Richerby
la source

À strictement parler, le polynôme de la deuxième puce doit être choisi une fois pour toutes, il ne peut pas dépendre de et . ;)

x

$x$

y

$y$

Martin Berger

Quelle est exactement la définition d'EXPTIME? Je m'en souviens comme , mais votre réponse semble supposer . Il n'est pas évident que le polynôme supplémentaire puisse être inclus sans en faire une classe de complexité différente.

O (k^{| x |})

$O(k^{|x|})$

O (k^{p (| x |)})

$O(k^{p(|x|)})$

kasperd

@kasperd Selon Wikipedia, EXPTIME est défini comme étant les problèmes de décision qui peuvent être résolus dans .

O (k^{p (| x |)})

$O(k^{p(|x|)})$

tparker

Pourquoi NP est-il dans EXPTIME?

Réponses: