Maths et Délires
Des maths et des délires
 

Maths et Délires Index du Forum

 FAQFAQ   RechercherRechercher   Liste des MembresListe des Membres   Groupes d'utilisateursGroupes d'utilisateurs   S'enregistrerS'enregistrer 
 ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Complexité

 
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Mathématiques taupinales et supérieures
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 21 Nov 2007, 14:13    Sujet du message: Répondre en citant

Ç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
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 21 Nov 2007, 15:11    Sujet du message: Répondre en citant

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


Dernière édition par Thibaut le 21 Nov 2007, 20:47; édité 7 fois
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 21 Nov 2007, 15:24    Sujet du message: Répondre en citant

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
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Aleph
Être humain normal


Inscrit le: 15 Nov 2007
Messages: 9
Localisation: Paris, France

MessagePosté le: 21 Nov 2007, 19:04    Sujet du message: Répondre en citant

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]??"
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 21 Nov 2007, 19:13    Sujet du message: Répondre en citant

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
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 21 Nov 2007, 20:04    Sujet du message: Répondre en citant

Aleph a écrit:
Le problème [tex:b749a374d0]P=NP[/tex:b749a374d0] est sur la roue du millionaire du Clay Institute non?
Il l'avait dit Mr. Green
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Mathématiques taupinales et supérieures Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com