Qu'est-ce qui est non déterministe dans NP exactement?

Question

J'étudie NP-complétude et j'ai une question sur la définition des problèmes NP.

Matériel dit

nondéterministe fait référence au fait qu'une solution peut être deviné à de polynomiale de nombreuses options en O (1) Temps

Ici, qu'est-ce que cela signifie par polynomially many options in O(1) time?

Par exemple, dans le cas du fameux problème 3SAT, n'y a-t-il pas un nombre exponentiel d'options?
(chaque littéral peut B.C. être true ou false et s'il y sont n littéraux, le nombre total d'options sont 2*2*2* ... * 2 = 2^n)

Cependant, il dit problème 3SAT est un problème NP. Comment peut-il être un problème NP même si il y a exponentionally de nombreux certificats?

Merci

Answer 1

Cette citation semble être une façon bizarre de phrasé, mais il peut se rapporter à quelque chose de similaire à être en mesure de choisir un nombre aléatoire entre 1 et n en O (1) - il y a n possibilités , mais en choisir seulement un prend O (1). Voir aussi: nondeterministic algorithms. "Temps polynomial non déterministe" est la définition complète de NP - "temps polynomial" est important - chaque décision que vous prenez pourrait prendre O (1), mais il y a polynomial beaucoup de ces décisions, conduisant à quelque chose qui peut théoriquement être résolu en temps polynomial, si vous pouvez faire le bon choix à chaque étape ou exécuter toutes les options en même temps.

Imaginez un arbre k-aire avec la hauteur p (n). Vous pouvez obtenir la feuille correcte dans O (p (n)) si vous choisissez (au hasard) l'enfant correct à chaque étape de la racine, ou si vous pouvez en quelque sorte visiter tous les chemins simultanément. Bien sûr, en pratique, vous ne pouvez pas compter sur des choix aléatoires corrects, et vous n'avez pas infiniment de processeurs - si vous deviez visiter tous les nœuds séquentiellement, cela prendra O (k ^{p (n)}).

---

Pour 3SAT, nous pouvons choisir au hasard vrai ou faux pour chaque littéral, ce qui nous conduit à un algorithme polynomial qui produirait le résultat correct si tous nos choix aléatoires étaient corrects.