QCM - Décidabilité et complexité

QCM - Décidabilité et complexité

Question 1. Quelle est la classe de complexité d'un problème dont on peut vérifier une solution en temps polynomial ?

$P$$NP$$NP$-complet$EXP$

Question 2. Quelle relation est vraie concernant $P$ et $NP$ ?

$P = NP$$P \subset NP$$NP \subset P$$P$ et $NP$ sont disjoints

Question 3. Un problème est $NP$-complet si :

Il appartient à $P$Il appartient à $NP$ et tout problème de $NP$ se réduit à lui en temps polynomialIl n'appartient pas à $NP$Il est résoluble en temps exponentiel

Question 4. Quelle est la complexité de $2^n + 25n^3$ en notation $O$ ?

$O(n^3)$$O(2^n)$$O(n^3 \cdot 2^n)$$O(n)$

Question 5. Un problème est décidable si :

Il peut être résolu en temps polynomialIl existe un algorithme qui termine toujours et répond correctementIl appartient à $NP$Il peut être vérifié en temps polynomial

Question 6. Le problème SAT (satisfiabilité d'une formule booléenne) est :

Dans $P$$NP$-completNon décidableDans $EXPTIME$ mais pas dans $NP$

Question 7. Quelle opération n'est PAS une opération élémentaire en $O(1)$ ?

Addition de deux entiersComparaison de deux entiersTri d'un tableau de $n$ élémentsAccès à un élément d'un tableau

Question 8. Si un problème $A$ se réduit polynomialement à un problème $B$, et $B \in P$, alors :

$A \in NP$-complet$A \in P$$A \notin NP$On ne peut rien conclure