🧩

Problèmes NP-complets

Chapitre 10 • Classes P & NP, Sudoku & Réductions

Statut : Prêt à jouer
Chapitre 10

Problèmes NP-complets

Étude détaillée des classes de complexité P et NP, du problème du Sudoku, des transformations (réductions) polynomiales et de la NP-complétude.

Quel est le titre exact du chapitre 10 ?

#1/12

Quelle est l'une des sept conjectures mathématiques majeures de la Fondation Clay mentionnée dans l'introduction ?

#2/12

Comment définit-on intuitivement un problème de la classe P par rapport à un problème NP-dur ?

#3/12

Quelles sont les deux applications majeures lorsqu'on identifie qu'un problème est difficile ?

#4/12

Comment le problème du Sudoku est-il défini formellement dans le cours ?

#5/12

Pourquoi l'algorithme non-déterministe du Sudoku (choix des valeurs puis vérification) appartient-il à la classe NP ?

#6/12

Quelle est la complexité de l'algorithme déterministe naïf qui explore toutes les grilles possibles pour le Sudoku ?

#7/12

Qu'est-ce qu'une transformation polynomiale (ou réduction polynomiale) de $L_1$ vers $L_2$ (notée $L_1 \alpha L_2$) ?

#8/12

Quelle est la propriété fondamentale des réductions polynomiales concernant la classe P ($L_1 \alpha L_2$) ?

#9/12

Qu'est-ce qu'un langage $L$ NP-complet ?

#10/12

Quelle serait la conséquence majeure s'il existait un langage NP-complet décidable par un algorithme polynomial ?

#11/12

Comment définit-on formellement un problème appartenant à la classe P pour les questions théoriques ?

#12/12