Maths et Délires

[Thibaut]

Ça veut dire quoi, ça ? Que tu ne sais pas ce que sont ces classes complexité ?

*[tex:4f8912b45e]\mathrm P[/tex:4f8912b45e] (comme Polynomial time) est la classe des problèmes décidables en temps polynomial sur des machines de Turing déterministes.
* [tex:4f8912b45e]\mathrm {NP}[/tex:4f8912b45e] (comme Non-deterministic Polynomial time) est la classe des problèmes décidables en temps polynomial, sur des machines de Turing non-déterministes.

Ensuite, on définit la hiérarchie polynomiale ainsi :
* [tex:4f8912b45e]\Sigma_0^P = \mathrm P[/tex:4f8912b45e]
* Pour [tex:4f8912b45e]k \in \mathbb N[/tex:4f8912b45e], on pose :
- [tex:4f8912b45e]\Sigma_{k+1}^P = \mathrm {NP}^{\Sigma_k^P}[/tex:4f8912b45e]
Où l'on note, pour [tex:4f8912b45e]\mathrm C[/tex:4f8912b45e] classe de problèmes, [tex:4f8912b45e]\mathrm {NP}^C[/tex:4f8912b45e] la classe des problèmes décidables en temps polynomial par des machines de Turing non-déterministes, auxquelles on a adjoint la possibilité de résoudre en une seule étape l'un des problèmes de [tex:4f8912b45e]\mathrm C[/tex:4f8912b45e] (on parle de machines à oracle dans [tex:4f8912b45e]\mathrm C[/tex:4f8912b45e]).

Ensuite, on note, pour [tex:4f8912b45e]k \in \mathbb N[/tex:4f8912b45e], [tex:4f8912b45e]\Pi_k^P = \text {co-} \Sigma_k^P[/tex:4f8912b45e], ie la classe des négations des problèmes de [tex:4f8912b45e]\Sigma_k^P[/tex:4f8912b45e].

On définit encore [tex:4f8912b45e]\mathrm {PH} = \bigcup\limits_{k \in \mathbb N} \Sigma_k^P = \bigcup\limits_{k \in \mathbb N} \Pi_k^P[/tex:4f8912b45e] (PH comme Polynomial Hierarchy).

Ces classes sont emboîtées ([tex:4f8912b45e]\forall k \in \mathbb N, \Sigma_k^P \subset \Sigma_{k+1}^p \cap \Pi_{k+1}^P[/tex:4f8912b45e]).

La conjecture à laquelle presque tous les spécialistes croient, c'est que toutes ces inclusions sont strictes. Mais personne ne sait en démontrer une seule. La plus facile d'entre elles, [tex:4f8912b45e]\mathrm P \subsetneq \mathrm {NP} \cap \text {co-}\mathrm {NP}[/tex:4f8912b45e], est déjà plus difficile que [tex:4f8912b45e]\mathrm P \subsetneq \mathrm {NP}[/tex:4f8912b45e], qui vaut un million de dollars...

Le théorème que l'on a montré s'énonce ainsi :
Soit [tex:4f8912b45e]k \in \mathbb N^*[/tex:4f8912b45e].
Si [tex:4f8912b45e]\Sigma_k^P = \Pi_k^P[/tex:4f8912b45e], alors [tex:4f8912b45e]PH = \Sigma_k^P = \Pi_k^P[/tex:4f8912b45e].

Si c'est le cas, on dit que la hiérarchie polynomiale s'effondre au rang [tex:4f8912b45e]k[/tex:4f8912b45e].
Si la hiérarchie ne s'effondre pas, toutes les inclusions ci-dessus sont strictes, et on dit que la hiérarchie est stricte.

Pour prouver ça, on utilise le lemme suivant :
Pour tout entier [tex:4f8912b45e]i[/tex:4f8912b45e], [tex:4f8912b45e]\Sigma_{i+1}^P[/tex:4f8912b45e] est la classe des problèmes [tex:4f8912b45e]P[/tex:4f8912b45e] tels qu'il existe [tex:4f8912b45e]Q \in \Pi_i^P[/tex:4f8912b45e], et [tex:4f8912b45e]k \in \mathbb N[/tex:4f8912b45e] tel que [tex:4f8912b45e]P = \{x, \exists y, \vert y \vert \leq \vert x \vert^k \wedge (x, y) \in Q\}[/tex:4f8912b45e] ([tex:4f8912b45e]\vert x \vert[/tex:4f8912b45e] désigne la longueur de [tex:4f8912b45e]x[/tex:4f8912b45e]).
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal

[Thibaut]

Ensuite, pour parler du deuxième théorème, il faut se farcir les définitions de [tex:0c6f1179a7]\mathrm {BPP}[/tex:0c6f1179a7] et [tex:0c6f1179a7]\mathrm P / \mathrm {poly}[/tex:0c6f1179a7], ce qui est quand même assez chiant.

Bon, allons-y. Je vous laisse imaginer la définition formelle d'un cricuit booléen (un truc qui contient des portes logiques, des entrées, des sorties, et qui n'a pas de boucle (genre on ne branche pas la sortie d'une porte sur l'entrée d'une porte qui la "précède")).
On peut coder les circuits par des chaînes de telle sorte que la longueur du codage soit un [tex:0c6f1179a7]\Theta(p+f+a)[/tex:0c6f1179a7], où [tex:0c6f1179a7]p[/tex:0c6f1179a7] est le nombre total de portes utilisées, [tex:0c6f1179a7]f[/tex:0c6f1179a7] le nombre total de fils, et [tex:0c6f1179a7]a[/tex:0c6f1179a7] l'arité maximale d'un fil ou d'une porte (arité d'une porte : nombre d'entrées ; arité d'un fil : nombre de sorties). On appellera cette grandeur (définie à un [tex:0c6f1179a7]\Theta[/tex:0c6f1179a7] près), la taille du circuit.

[tex:0c6f1179a7]\mathrm P/\mathrm {poly}[/tex:0c6f1179a7] est la classe des problèmes [tex:0c6f1179a7]P[/tex:0c6f1179a7] tels qu'il existe une famille [tex:0c6f1179a7](\mathcal C_n)_{n \in \mathbb N}[/tex:0c6f1179a7] de circuits booléens, et un polynôme [tex:0c6f1179a7]Q[/tex:0c6f1179a7] tel que, pour tout [tex:0c6f1179a7]n \in \mathbb N[/tex:0c6f1179a7], le circuit [tex:0c6f1179a7]\mathcal C_n[/tex:0c6f1179a7] :
- a exactement [tex:0c6f1179a7]n[/tex:0c6f1179a7] entrées (totalement ordonnées),
- a exactement une sortie,
- est de taille majorée par [tex:0c6f1179a7]Q(n)[/tex:0c6f1179a7],
- [tex:0c6f1179a7]\mathcal C_n[/tex:0c6f1179a7] décide les instances de taille [tex:0c6f1179a7]n[/tex:0c6f1179a7] de [tex:0c6f1179a7]P[/tex:0c6f1179a7], c'est-à-dire que pour toute instance [tex:0c6f1179a7]x[/tex:0c6f1179a7] (supposée être une suite de bits) de [tex:0c6f1179a7]P[/tex:0c6f1179a7] de taille [tex:0c6f1179a7]n[/tex:0c6f1179a7], lorsqu'on branche les entrées de [tex:0c6f1179a7]\mathcal C_n[/tex:0c6f1179a7] sur [tex:0c6f1179a7]x[/tex:0c6f1179a7], la sortie du circuit s'évalue en 1 si [tex:0c6f1179a7]x \in P[/tex:0c6f1179a7], et 0 sinon.

Cette classe contient [tex:0c6f1179a7]\mathrm P[/tex:0c6f1179a7], mais aussi des problèmes indécidables (et même beaucoup : elle a la puissance du continu, tout comme l'ensemble de tous les problèmes, alors que l'ensemble des problèmes décidables n'est que dénombrable).
Elle est stable par complémentation.
Par contre, elle ne contient pas [tex:0c6f1179a7]\mathrm {EXPTIME}[/tex:0c6f1179a7], et on ne sait pas si elle contient [tex:0c6f1179a7]\mathrm {NP}[/tex:0c6f1179a7] ou non. Le théorème suivant, combiné avec le précédent, amène la conjecture que ce n'est pas le cas.

Maintenant, les machines randomisées :
Ce sont des machines de Turing déterministes, auxquelles ona adjoint une bande, dit bande d'aléa.
Cette bande reçoit initialement un mot infini, et, chaque étape, la machine doit avancer la tête de lecture qu'elle a sur cette bande, d'au moins une case.
Pour [tex:0c6f1179a7]r[/tex:0c6f1179a7] un mot infini, et [tex:0c6f1179a7]x[/tex:0c6f1179a7] un mot fini, on dit que la machine randomisée [tex:0c6f1179a7]M[/tex:0c6f1179a7] accepte [tex:0c6f1179a7]x[/tex:0c6f1179a7] sur l'aléa [tex:0c6f1179a7]r[/tex:0c6f1179a7], ou que [tex:0c6f1179a7]M(x, r)[/tex:0c6f1179a7] accepte lorsque [ce qu'on pense].
On met la tribu des cylindres sur l'ensemble des mots infinis, et la probabilité uniforme [tex:0c6f1179a7]\mathbb P[/tex:0c6f1179a7] dessus.

Maintenant, [tex:0c6f1179a7]\mathrm {BPP}[/tex:0c6f1179a7] (pour Bounded Probability of error in Polynomial time) est la classe des problèmes [tex:0c6f1179a7]P[/tex:0c6f1179a7] tels qu'il existe une machine randomisée [tex:0c6f1179a7]M[/tex:0c6f1179a7], un polynôme [tex:0c6f1179a7]Q[/tex:0c6f1179a7] tels que, pour toute entrée [tex:0c6f1179a7]x[/tex:0c6f1179a7] de taille [tex:0c6f1179a7]n[/tex:0c6f1179a7] :
* pour tout aléa [tex:0c6f1179a7]r[/tex:0c6f1179a7], [tex:0c6f1179a7]M(x, r)[/tex:0c6f1179a7] termine en temps [tex:0c6f1179a7]\leq Q(n)[/tex:0c6f1179a7],
* si [tex:0c6f1179a7]x \in P[/tex:0c6f1179a7], alors [tex:0c6f1179a7]\mathbb P_r [M(x, r) \text { n'accepte pas}] \leq \frac 1 3[/tex:0c6f1179a7],
* si [tex:0c6f1179a7]x \not\in P[/tex:0c6f1179a7], alors [tex:0c6f1179a7]\mathbb P_r[M(x, r) \text { accepte}] \leq \frac 1 3[/tex:0c6f1179a7].

Notons que l'on peut remplacer [tex:0c6f1179a7]\frac 1 3[/tex:0c6f1179a7] par n'importe quelle constante strictement comprise entre [tex:0c6f1179a7]0[/tex:0c6f1179a7] et [tex:0c6f1179a7]\frac 1 2[/tex:0c6f1179a7].

On a bien sûr :
* [tex:0c6f1179a7]\mathrm P \subset \mathrm {BPP}[/tex:0c6f1179a7].
* [tex:0c6f1179a7]\mathrm {BPP} = \text {co-} \mathrm {BPP}[/tex:0c6f1179a7]

Euh, plus le temps d'énoncer les autres théorèmes d'aujourd'hui...
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal

[Thibaut]

Théorèmes :

* [tex:28f9e30d3b]\mathrm {BPP} \subset \mathrm P/\mathrm {poly}[/tex:28f9e30d3b].

* (Karp-Linton) : Si [tex:28f9e30d3b]\mathrm {NP} (=\Sigma_1^P) \subset \mathrm P/\mathrm {poly}[/tex:28f9e30d3b], alors [tex:28f9e30d3b]\mathrm {PH} \subset \mathrm P/\mathrm {poly}[/tex:28f9e30d3b].

De plus : si [tex:28f9e30d3b]\mathrm {NP} (=\Sigma_1^P) \subset \mathrm P/\mathrm {poly}[/tex:28f9e30d3b], alors [tex:28f9e30d3b]\Pi_2^P = \Sigma_2^P[/tex:28f9e30d3b] (auquel cas la hiérarchie polynomiale s'effondre, cf plus haut).

* [tex:28f9e30d3b]\mathrm {BPP} \subset \Pi_2^P \cap \Sigma_2^P[/tex:28f9e30d3b].
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal

[Aleph]

Le problème [tex:6d14ca2630]P=NP[/tex:6d14ca2630] est sur la roue du millionaire du Clay Institute non?
_________________
"I'm [tex:13637998bc]sin^2(x)[/tex:13637998bc], you're [tex:13637998bc]cos^2(x)[/tex:13637998bc], together, we can be one."

"What the [tex:13637998bc]f(x)[/tex:13637998bc]??"

[Thibaut]

Oui.
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal

[Jill-Jênn]