Bonjour,
Je précise que je n'ai aucune compétence en informatique, donc je risque de sortir des inanités...
Pourriez-vous me dire si j'ai bien compris ou non le problème :
N = problème résolvable en temps polynomial par une machine déterministe, donc résolvable en un temps raisonnable par les machines du Turing - qui sont des machines déterministes c'est à dire qu'elles ne choisissent pas un chemin parmi d'autres pour résoudre un problème, mais bien un seul algorithme prédéfini..
NP = problème résolvable en temps polynomiale mais cette fois par des machines non-déterministes, c'est à dire des machines qui n'existent pas actuellement (j'ai un doute sur cette affirmation...), qui résolve un problème en choisissant l'algorithme prenant le moins de temps et d'espace parmi d'autres.

Donc l'ensemble P est inclus dans l'ensemble NP, mais on doit, pour prouver que P = NP, démontrer que NP est inclus dans P c'est à dire.

Ai-je bien compris...?

(Merci à DingiDing de m'avoir fait découvrir ce problème )

ouais c'est ca.

Precision: Les machines de Turing non deterministe executent TOUTES les branches en meme temps et s'arretent des qu'une des branches s'arrete. Naturellement, on a pas vraiment de machine non deterministe dans la vraie vie.

Merci Godrik.
Peut-être pourrais-tu m'éclairer sur un autre point : les machines non déterministes mais résolvant les problèmes en temps exponentielle cette fois existent-elle ?

Et une dernière demande de précision : N appartient à NP car on peut assimiler un problème N à un problème NP qui n'aurait qu'une "branche" ?

Si par "exister" tu veux dire que l'on peut en fabriquer dans la vraie vie, non, elles n'existent pas. Les machines de Turing non-déterministes sont un modèle de calcul abstrait, pour en simuler une en vrai comme l'a dit godrik il faudrait faire toutes les exécutions en parallèle, et ce n'est pas possible.

Par contre, il existe (au sens mathématique / abstrait de "existe") des machines de turing non-déterministes qui calculent en temps exponentiel. La classe de complexité correspondante s'appelle NEXP. D'ailleurs, la question de savoir si EXP = NEXP est ouverte également, au même titre que P = NP.

En fait, si le problème "P = NP" est si connu, c'est principalement parce que les algos polynomiaux sont ceux que l'on aime bien avoir en informatique, c'est là que les temps d'exécution sont le plus souvent "acceptables" à l'échelle humaine. Ca, et le fait qu'il soit parmi les "7 problèmes du millénaire"
Mais il y a plein d'autres classes de complexité, et plein de questions ouvertes sur leurs relations. Tu peux regarder cette page vite fait, elle référence la plupart (toutes ?) les classes intéressantes qui existent à l'heure actuelle.
https://complexityzoo.uwaterloo.ca/Complexity_Zoo

Lowenheim :
"Les machines de Turing non-déterministes sont un modèle de calcul abstrait, pour en simuler une en vrai comme l'a dit godrik il faudrait faire toutes les exécutions en parallèle, et ce n'est pas possible."
En soi, en mettant plusieurs machines de Turing déterministes en réseau, qui résoudraient ensemble un même problème avec des algorithmes différents (emprunteraient donc plusieurs "branches"), on obtiendrait ainsi une machine de Turing non-déterministe ?

Je me doute que la réalité est loin d'être aussi simple, mais je me demande en quoi mon hypothèse est fausse !

On parle un peu dans le vide là, le plus simple serait de regarder la définition formelle d'une machine de Turing déterministe et non-déterministe pour voir la différence.
C'est vraiment élémentaire comme truc, pas besoin d'avoir fait d'études avancées pour comprendre, surtout qu'il y a des moyens très basiques de réprésenter tout ça avec des dessins.
Tu peux regarder un peu ce bouquin par exemple si tu as pas peur de l'anglais : http://www.icsd.aegean.gr/kaporisa/index_files/sipser.pdf . Sinon, wikipedia devrait pas etre trop compliqué non plus.

Sinon, un autre caractérisation équivalente et peut être moins compliquée à concevoir de la classe NP :
Un problème est en NP si il existe une machine de Turing déterministe qui arrive à vérifier une solution en temps polynomial.
En gros, ta machine "devine" la solution au problème (c'est là que se cache le non-déterminisme), et ensuite elle la vérifie en temps polynomial.

C'est ce "devine" qu'on ne peut pas simuler dans la réalité : tout ce qu'on peut faire, c'est d'essayer toutes les possibilités en parallèle.

Merci pour le lien !

Justement c'est en me rendant sur la page wiki des Turings non déterministes (http://fr.wikipedia.org/wiki/Machine_de_Turing_no
n_d%C3%A9terministe)
que j'ai lu :
une machine de Turing non déterministe peut être simulée par une machine de Turing déterministe. Toutefois la complexité des calculs diffère
Du coup, néophyte que je suis, je ne comprend toujours pas en quoi une machine non-déterministe n'est pas possible à réaliser !

"Un problème est en NP si il existe une machine de Turing déterministe qui arrive à vérifier une solution en temps polynomial."
Tu voulais dire non déterministe ?

Non, c'est bien "déterministe", justement !

Calculer la solution de manière non-déterministe
<=> Savoir vérifier une solution de manière déterministe

"Vérifier" dans le sens où la machine prend en entrée un problème et sa solution, et doit répondre si "oui" ou "non" la solution est correcte.

Et oui en effet, on peut simuler une machine non-déterministe par une machine déterministe. En fait, la différence c'est qu'une machine non-déterministe peut lancer tout plein de calculs différents en même temps, et si l'un d'entre eux aboutit, elle s'arrête. La machine déterministe peut simuler ça en faisant tous les calculs l'un après l'autre, mais ça prend plus de temps.

Quand on disait qu'on ne pouvait pas faire de machine non-déterministe dans la réalité, c'est parce qu'on ne peut pas simuler le fait de faire tous les calculs en même temps. Mais on peut les faire l'un après l'autre.

Quelques commentaires:

"Et une dernière demande de précision : N appartient à NP car on peut assimiler un problème N à un problème NP qui n'aurait qu'une "branche" ?"

Les probleme de N ca n'existe pas, c'est P et NP Mais oui c'est pour ca que P \in NP

"Les machines de Turing non-déterministes sont un modèle de calcul abstrait, pour en simuler une en vrai comme l'a dit godrik il faudrait faire toutes les exécutions en parallèle, et ce n'est pas possible."
En vrai, il y a des gens qui ont essayer a base de reaction chimique de faire une genre de machine non deterministe. Mais ce n'est pas aller bien loin.

"En fait, si le problème "P = NP" est si connu, c'est principalement parce que les algos polynomiaux sont ceux que l'on aime bien avoir en informatique, c'est là que les temps d'exécution sont le plus souvent "acceptables" à l'échelle humaine"
Dans la vraie vie des que les algos sont plus que lineaire, les gens abandonne les implemetations sur des gros jeu de donne. De nos jours, les problemes "big data" on des taille en millions ou en milliard, donc un algo en n^3, c'est pas utilisable.

"Sinon, un autre caractérisation équivalente et peut être moins compliquée à concevoir de la classe NP : Un problème est en NP si il existe une machine de Turing déterministe qui arrive à vérifier une solution en temps polynomial."
Dans les trucs lie a ca, tu as le PCP theorem qui est assez interessant aussi.

Salut, ravi que le sujet te plaise ;o

Essaie de lire https://interstices.info/jcms/c_21832/p-np-un-probleme-a-un-million-de-dollars?hlText=p+np

Lowenheim : Ok j'avais pas saisi la nuance Calculer / Vérifier ! Merci.

Godrik : En soi, le PCP theorem permet, non pas de résoudre un problème NP avec une machine déterministe et en temps polynomiale, mais de contourner le problème P = NP en simplifiant la tâche de vérification d'une machine de Turing déterministe grâce à un PCP ?
Là encore j'ai peut-être mal formulé... D'ailleurs (on n'est plus vraiment dans la question du P = NP mais bon), je pense avoir mal saisi cette notion de vérification car il s'agit d'une vérification et non d'un calcul !
Le PCP theorem, qui est censé permettre la simplification d'une tâche qui normalement serait exécutée en temps exponentielle, ne permet en fait que la vérification de la solution ? Or cette tâche de vérification n'est normalement pas longue et est réalisable par une machine déterministe en temps polynomiale non ?
Donc en quoi cette technique permet de contourner P = NP (comme j'ai pu le lire) ?

Dingiding : Merci pour ton lien ! )

Vous pensez que dans un futur proche (ou éloigné) on pourra utiliser l'ordinateur quantique pour résoudre ce problème puisque apparemment si on écoute ce qui se dit sur cette ordinateur, il pourrait être capable de simuler une machine non-déterministe ?

D'ailleurs c'est quoi l'intérêt d'une machine de Turing ? Ça ne ressemble même pas à un ordinateur ce bordel...

La problème P = NP est encore une fois un problème théorique qui parle de machines abstraites. Le fait de pouvoir ou non fabriquer des machines non-déterministes dans la vraie vie n'y change rien, et le fait d'avoir ou non des ordinateurs quantiques non-plus. C'est un problème mathématique qui se résout avec une démonstration, pas avec une avancée technologique.

Quand on parle d'ordinateurs quantiques, on parle d'autres classes de complexité : par exemple, BQP (Bounded Quantum Polynomial time) ou bien QMA (Quantum Merlin Arthur), et encore beaucoup d'autres.

Ce qu'on sait, c'est qu'il y a des problèmes telles que la factorisation d'entiers, que l'on ne sait pas résoudre en temps polynomial (déterministe), mais qu'on sait résoudre en temps polynomial sur un ordinateur quantique (avec l'algorithme de Shor). C'est à dire qu'on ne sait pas si le problème de factorisation d'entiers est dans P, mais on sait qu'il est dans BQP. De manière plus générale, on sait que P est inclus dans BQP.

Y'a un joli dessin sur wikipedia qui explique les relations supposées entre certaines classes :
http://upload.wikimedia.org/wikipedia/commons/1/1d/BQP_complexity_class_diagram.svg?uselang=fr
Mais les inclusions ne sont pas forcément strictes, par exemple si on a P=NP ça change totalement le dessin...

Jean-Electron, justement c'est ce qui est interessant dans la machine de turing. Bien qu'elle ne ressemble pas a un ordinateur tel qu'on les connait, elle n'est pas differente d'un ordinateur en terme de capacite de calcul. En supposant que ton ordinateur a une memoire infinie, ton ordinateur a exactement la meme puissance de calcul qu'une machine de turing (a un facteur polynomial pres).

Cette abstraction permet de repondre a des question comme: est ce qu'il y a des choses qui sont calculable avec machine A mais qui ne sont pas calculable avec machine B? Si tu peux montrer l'equivalence de A et de B a une machine de turing, alors tu as montrer que les machine ne sont pas fondamentalement differente: tu peux emuler l'une avec l'autre. On a pu montrer que certaines machines sont strictement moins puissante qu'une machine de turing.

Montrer ce genre de chose dans les annees 50 ce n'etait pas forcement gagne. C'etait une epoque ou plein de machine de calcul differente apparaissait. Pouvoir classer les machines entre turing equivalent et pas turing equilavent etait important. C'est d'autant plus interessant que l'on arrive a des machines quantiques qui a priori ne seront pas equivalente a des machines de turing et qui permettront donc de faire des choses fondamentalement differente.

Aussi les machines de turing sont la base de l'algorithmique. Tu ne peux reflechir a des algorithmes de facon abstraite que parceque tu sais les machines sur lesquelles tu vas implementer ces algorithms sont toutes turing equivalente. Du fait tu n'as pas besoin de construire des algorithmes pour chaque machine.

Finalement, la notion de machine de turing a permi d'extraire la classe de probleme NP-Complet. Ca nous donne une comprehension assez claire de pourquoi certains problemes peuvent etre resolu avec un algorithme polynomial alors que l'on arrive pas a en trouver pour certains autres probleme.

Bref la machine de turing n'a pas pour vocation a etre construite, mais a nous donner un modele theorique surlequel on peut reflechir a la resolution de certains probleme.

"des machines quantiques qui a priori ne seront pas equivalente a des machines de turing"

Tu en es sur ? Il me semblait qu'en termes de calculabilité le fait de travailler sur des machines quantiques n'apportait rien. Je n'ai pas de source, donc je peux me tromper

a priori c'est non deterministe une machine quantique et ca peut manipuler simultanement une infinite d'etat quantique. Moralement c'est analogique comme truc. Apres, ce que je dis toujours au sujet des machines quantiques, c'est que j'attends dans avoir une sur laquelle je peux me logguer avant de me poser plus de question.

C'est vraiment chelou l'informatique théorique

Puisqu'il est question d'ordinateur quantique, je me demandais : l'ordinateur quantique pourrait résoudre des problèmes Exp et NP grâce à la fonction de superposition des états quantiques (les qubits) ?
D'après ce que j'ai pu lire : n qubits permettrait à l'ordinateur de lire 2^n états à la fois, contre un état parmi 2^n pour un ordinateur classique.
Avec 2 bits :
- Ordi classique : 00, 01, 10 ou 11
- Ordi quantique : Tous ces états à la fois.

En fait, l'ordinateur quantique donne la probabilité de chacun des résultats possibles pour lire l'information porté par le qubit ?

Oui c'est à peu près ça "l'idée intuitive" derrière la notion d'ordinateur quantique. Après, si on veut voir concrètement à quoi ressemble un algorithme quantique il faut faire un peu de méca Q et d'algèbre linéaire. Un qubit ce n'est pas exactement comme une distribution de probabilités.

Et niveau théorie de l'information également y'a pas mal de subtilités qui font que ce n'est pas aussi simple que "avoir tous les états à la fois". Lorsque tu mesures un qubit, tu le détruis, et il y a des propriétés (par exemple, le non-clonage) qui font que tu ne peux pas refaire ta mesure autant de fois que tu le veux.

On peut faire des algorithmes intelligents grâce aux ordinateurs quantiques, mais ce n'est pas immédiat, on n'a pas de façon directe de simuler une machine de Turing non-déterministe sur une machine quantique.