Temps polynomial

[Bergame]

Il y a quelques matheux parmi nous. Est-ce que quelqu'un pourrait avoir la patience et la bonté de m'expliquer en termes simples ce qu'est le temps polynomial ?

[Saint-Ex]

Il y a quelques matheux parmi nous. Est-ce que quelqu'un pourrait avoir la patience et la bonté de m'expliquer en termes simples ce qu'est le temps polynomial ?

Je ne savais pas ce qu'était le temps polynomial. Alors ma curiosité a pris le dessus.

Je me suis d'abord penché sur la première leçon de mathématiques qui m'a semblé sérieuse sur la seule expression «polynomial».

Voilà ce qu'en dit un mathématicien qui a l'air de connaître son métier :



Mais si on manque d'exercice pour comprendre ce que nous dit ce mathématicien, alors on sera intéressé par la vulgarisation extrême mais exacte de ce qu'est en réalité une expression polynomiale.



Inutile de résoudre le problème posé par cette illustration. Il suffit de comprendre que les objets à emporter sont d'un nombre à découvrir et surtout de poids différents.

Chaque objet à emporter est un monôme mathématique, s'il y a plusieurs objet à emporter, l'ensemble de ses objets est un polynomial mathématique.

Le temps de calcul nécessaire pour résoudre le problème posé, c'est ça, le temps polynomial.

.

Ah, j'allais oublier, le temps polynomial est un élément d'importance en informatique ...

.

[Bergame]

Merci, Saint-Ex !
Oui, figure-toi que je cherche à comprendre comment fonctionnent les IA....

[AntiSubjectiviste]

Il y a quelques matheux parmi nous. Est-ce que quelqu'un pourrait avoir la patience et la bonté de m'expliquer en termes simples ce qu'est le temps polynomial ?

L'expression "temps polynomial" provient de la théorie de la complexité, qui est une branche de l'informatique théorique. Dans ce contexte, le mot "temps" désigne le nombre d'instructions qu'un algorithme doit exécuter pour produire son résultat.

Dans le cas d'un algorithme qui requiert un input de l'utilisateur, son temps d'exécution est une fonction f(n) de la taille n de cet input, et ce temps est dit polynomial si cette fonction est un polynôme en la variable n. (Un polynôme en la variable n est un calcul constitué de sommes ou de produits de constantes et de la variable n.) Quand c'est le cas, on dit que cet algorithme est de complexité polynomiale.

L'idée, c'est qu'un algorithme de complexité polynomiale est un algorithme dont le temps d'exécution n'augmente pas trop lorsque la taille de son input augmente; c'est donc un algorithme considéré comme "efficace" ou "performant", théoriquement parlant.

[Bergame]

Merci, AS.
Si je comprends un peu : Un algorithme se définissant entre autres choses par sa finitude et sa consommation en capacité de mémorisation, le but est de réaliser des algorithmes qui garantissent soit l'aboutissement à une solution correcte d'un problème défini, soit l'aboutissement à un état de non-solution, et ce dans le temps le plus court possible avec la consommation de capacité et d'énergie la plus économe possible (?)
Dans cette perspective, les problèmes de classe NP (non-déterministes en temps polynomial) sont des problèmes auxquels on ne peut parvenir à ce double aboutissement en temps polynomial.
Mais alors, cela signifie qu'il existe une mesure du temps polynomial ? Je veux dire : Il existe une durée maximale du temps polynomial au-delà de laquelle on estime : Ce problème X n'est pas déterministe en temps polynomial ?

[Kercos]

L'idée, c'est qu'un algorithme de complexité polynomiale est un algorithme dont le temps d'exécution n'augmente pas trop lorsque la taille de son input augmente; .

Je dois me planter mais ça ressemble à la notion d'attracteur: le nombre suffisant d'entrées (variables et constantes) pour définir (cerner) correctement l'attracteur.

[Saint-Ex]

.

À propos d'intelligence artificielle, Peggy Sastre m'informe d'une petite pensée (du jour bonjour) de la part d'un des ses collègues de travail, Yascha Mounk :

«Les nouveaux outils de génération d’images et de textes par IA sont bourrés de biais woke qui déforment la réalité.»

Qui est Yascha Mounk ? Voir ici :

https://www.yaschamounk.com

.

[maraud]

En électronique, le temps se mesure, se matérialise par une quantité de courant: lorsqu'un courant électrique remplit un réservoir, on compte une unité au moment précis où ce courant cesse de circuler parce que le réservoir en question est plein. C'est une "base-temps" ex: un condensateur talonné par une résistance , on a alors deux inconnues à ajouter aux polynômes 1 la valeur ohmique de la résistance 2) la capacité en micro/nano/pico farad du condensateur. Pour obtenir un temps donné, on consomme la quantité de courant nécessaire. En informatique, Il en va de même pour toute information exploitée, elle se matérialise par la consommation ou non de courant  ( grosso modo 1 correspond à une conso de courant sous 5 volts, 0 correspond à une absence de conso.) . On comprend aisément que les polynômes qu'il faut envisager pour l'IA ne sont pas du second degré...

Il faut considérer que le temps dont il est question se présentera dans sa plus simple expression sous forme d'une équation à deux inconnues , donc déjà polynomial. ( on comprends aisément de quel niveau de complexité seront les algorithmes qui intégreront tous les sous-ensembles de comptages de temps dans les super-ordinateurs de l'IA. Au reste on a beau, sans cesse miniaturiser les composants, il y a hélas des seuils " physiologiques" indépassables pour nombre de composants qui requièrent toujours des tensions et intensités de courants importantes. D'où certaines astuces de délestages pour économiser l'énergie c'est pourquoi, enfin e l'imagine, on parle de "temps polynomial"...

[Bergame]

Salut maraud ! Merci.

une équation à deux inconnues , donc déjà polynomial.

C'est-à-dire qu'un polynôme, c'est une équation à plus d'une inconnue ?

[AntiSubjectiviste]

Merci, AS.  
Si je comprends un peu : Un algorithme se définissant entre autres choses par sa finitude et sa consommation en capacité de mémorisation, le but est de réaliser des algorithmes qui garantissent soit l'aboutissement à une solution correcte d'un problème défini, soit l'aboutissement à un état de non-solution, et ce dans le temps le plus court possible avec la consommation de capacité et d'énergie la plus économe possible (?)

Ce n'est pas ça du tout.
Pour comprendre les enjeux de la notion de "temps polynomial", il faut d'abord acquérir des notions préliminaires :

• ce qu'est une machine de Turing déterministe (ainsi qu'une machine de Turing non déterministe),
  
• ce qu'est un problème de décision,
  
• ce qu'est un algorithme,
  
• ce qu'est la complexité d'un algorithme (et la notion de "temps" associée).
  

Sur cette base, étant donné un problème, le but n'est pas d'en trouver un algorithme de résolution "rapide", mais plutôt d'en trouver un qui soit "peu complexe".

Dans cette perspective, les problèmes de classe NP (non-déterministes en temps polynomial) sont des problèmes auxquels on ne peut parvenir à ce double aboutissement en temps polynomial.
Mais alors, cela signifie qu'il existe une mesure du temps polynomial ? Je veux dire : Il existe une durée maximale du temps polynomial au-delà de laquelle on estime : Ce problème X n'est pas déterministe en temps polynomial ?

Ces questions n'ont aucun sens, parce que tu n'es pas familier avec les notions préliminaires ci-dessus. Un problème de classe NP est résoluble en temps polynomial, mais sur une machine de Turing non déterministe. Cela équivaut (mais ce n'est pas évident) à dire qu'un problème est de classe NP si la validité d'une proposition de solution est vérifiable en temps polynomial sur une machine de Turing déterministe.

J'écris ces phrases pour te donner des éléments de recherche d'information, mais je ne les expliquerai pas (trop long).

Exemple basique : le sudoku. Étant donné une grille de sudoku lacunaire, il est facile de vérifier qu'une proposition de solution (c.-à-d. un remplissage particulier des cases vides par des chiffres) est valide ou pas. Mais il est beaucoup plus difficile de trouver la bonne solution. Pourtant, il y a un algorithme pour cela : celui qui passe en revue tous les remplissages possibles jusqu'à tomber sur le bon. C'est juste que cet algorithme, bien que simple dans son principe, est extrêmement laborieux : il y a énormément de remplissages possibles et tous les passer en revue s'avère peu efficace (ça pourrait prendre bien plus que des milliards d'années...). Eh bien le problème du sudoku est un exemple de problème NP (je passe des détails).

Salut maraud ! Merci.

une équation à deux inconnues , donc déjà polynomial.

C'est-à-dire qu'un polynôme, c'est une équation à plus d'une inconnue ?

Non, ça n'a rien à voir, maraud raconte n'importe quoi. Voir Wikipédia.

[maraud]

Salut maraud ! Merci.

une équation à deux inconnues , donc déjà polynomial.

C'est-à-dire qu'un polynôme, c'est une équation à plus d'une inconnue ?

Salut Bergame,

S'cuse, je suis allé trop vite!

[maraud]

AntiSubjectiviste,

mea culpa!

[neopilina]

Salut Maraud !

Non, ça n'a rien à voir, maraud raconte n'importe quoi. Voir Wikipédia.

Toujours un peu " abrupt " le camarade A.S. : un matheux !

[maraud]

Salut Neo,

oui, AS a été expéditif!

je comprends néanmoins sa réaction ( il a raison!)

Le fait est que s'agissant de programmation informatique, la forme polynomiale n'est pas un simple polynômes, mais la "forme" polynomiale appliquée à des algorithmes... autant dire que c'est nettement plus complexe.

[Bergame]

Je finis par me demander s'il n'y a pas un lien entre l'égotisme et l'ignorance. Ce qui serait assez logique, du reste : Quand on est persuadé d'être plus intelligent que les autres, on n'a pas besoin d'apprendre.
Souviens-toi les mots de Socrate, neopilina : Tout ce que je sais, c'est que je ne sais pas.

Ok, merci AS. Je vais bosser un peu les pistes que tu proposes, et je reviens.

[neopilina]

Souviens-toi les mots de Socrate, neopilina : Tout ce que je sais, c'est que je ne sais pas.

Ce qui, comme chacun sait, est une paraphrase de Métrodore de Chio placée dans la bouche de Socrate par Platon.

P.S. Il y a sur ce forum la meilleure édition française des fragments de Métrodore de Chio, du nectar, on aurait tort de se priver !

[AntiSubjectiviste]

Le fait est que s'agissant de programmation informatique, la forme polynomiale n'est pas un simple polynômes

Si, c'est un simple polynôme.

[Bergame]

Ce qui, comme chacun sait, est une paraphrase de Métrodore de Chio placée dans la bouche de Socrate par Platon.

Pas du tout ! Je t'ai d'ailleurs déjà expliqué la différence entre les deux.
Le pire, c'est que tu ne tiens absolument aucun compte de ce qu'on te dit.

[maraud]

Bon,après mon malencontreux " pet verbal"....

Pour comprendre ce qu'est le temps polynomial il suffit de le comparer au temps non-polynomial, en l’occurrence le temps exponentiel: est polynomial le temps selon lequel s'exécute un algorithme dont la complexité temporelle s'élève à un seul exposant.( n exposant k) ces algorithmes sont disponibles et plutôt répandus. On parle alors de problèmes de classe" P" ( P pour "polynomial" peut-être ?)

Vient ensuite la classe des problèmes  "EXPTIME": Les algorithmes nécessaires sont une complexification des algorithmes de classe P , la complexité des algo.de classe P se voit augmentée d'un exposant à l'échelle supérieure   ( 2^n^ k) Là on attaque la zone extrêmement chronophage puisque le nombre  d'opérations nécessaires augmentent exponentiellement...

Pour un nombre d'instructions nécessaires en classe P  (polynomiales) de n ^2 ( pour n=10, on a 100 opérations)on passe en classe EXPRIM à 2^n^2 (on a alors 10^30 opérations).

Vient enfin entre la classe P et La classe EXPRIM une zone " grise" dite classe NP . ( où l'on rencontre des problèmes par toujours bien identifiables, mais que l'on peut éventuellement "vérifier" ( on vérifie les solutions plus qu'on ne les trouve)


Le temps polynomial est donc le temps économiquement/écologiquement le moins dispendieux, mais pas suffisant pour les problèmes qui requièrent un nombre d'opérations vertigineux. D'où le critère de vitesse pour évaluer un composant/module/ordi. Il faut noter que la notion de "temps" est corrélée à celle "d'espace"...

[maraud]

Dans cette perspective, les problèmes de classe NP (non-déterministes en temps polynomial) sont des problèmes auxquels on ne peut parvenir à ce double aboutissement en temps polynomial.
Mais alors, cela signifie qu'il existe une mesure du temps polynomial ? Je veux dire : Il existe une durée maximale du temps polynomial au-delà de laquelle on estime : Ce problème X n'est pas déterministe en temps polynomial ?

C'est apparemment le problème à un "million de dollars..."

Pour le temps polynomial ( en classe P) sa valeur est fixée par ^ k ( n étant le volume de données à traiter.) Pour un n=10, on a 10^2= 100 opérations et pour un n= 1000, on a 1million d'opérations.

Dans les opérations polynomiales le temps est fixé dans la formulation et ne peut aller au delà de ce que permet k.

.........................................................................................................................................
Dans le temps exponentiel, il grandit en s'accélérant  avec ce que cela peut impliquer... N'oublions pas qu'en informatique la cause et l'effet peuvent quasiment se superposer/confondre puisqu'on travaille quasiment à la vitesse de la lumière et que la finesse avec laquelle on œuvre dans les labos peut approcher l'électron lui-même , c'est-à-dire que dans ce cas " le messager devient le message" un peu comme si l'information s'émancipait de son support. Attention: là c'est une pure divagation de ma part

......................................................................................................................................

C'est bien dans la zone "grise" NP que les matheux travaillent à "unifier" les classes P, NP et EXPTIME pour résoudre, entre-autres choses, le problème que tu évoques et il y a bien un million de dollars de Prix à la clef. C'est dire...

Certains pensent qu'il faut s'en tenir à trouver des algorithmes suffisamment simples pour rester polynomiaux mais suffisamment performant pour faire un travail optimal d'une complexité de classe EXPTIME  ( ça fait un peu " game changer/arme magique"...), d'autres travaillent à élaborer/trouver de nouvelles classes  (esprit cartésien) d'autres encore envisagent un ordinateur quantique ( rêveur, visionnaires...?)

[Bergame]

Merci Maraud, mais je crois que tu es un peu en avance sur moi.
Dans un premier temps au moins, je vais m'efforcer de suivre le programme de recherche que me propose AS.

Qu'est-ce qu'une machine de Turing ?
En première approximation, une machine de Turing est une machine à calculer qui décide elle-même des opérations à effectuer.
Plus précisément : C'est une machine composée d'un "ruban" sur lequel est inscrite une suite de chiffes 0 ou 1 ; et d'une "table de transition", qui traduit successivement les 0 et 1 (entrées) en "états internes" qui, en sortie, déterminent une action : Soit continuer à lire le ruban, soit revenir en arrière sur le ruban, soit arrêter.
La table de transition est donc un algorithme. Et les états internes (ai-je cru comprendre) correspondent aux opérateurs booléens.
Mais Turing a démontré qu'il existe des machines de Turing dont la table de transition peut être écrite sur le ruban : Des machines de Turing "universelles". Ainsi, les machines de Turing universelles sont "programmables" -théorème qui a conduit à la distinction entre hardware et software.
(Je laisse pour l'instant la question de savoir ce qu'est une machine de Turing "déterministe" et surtout "non-déterministe", pas clair pour l'instant)

Qu'est-ce que le problème de la décision ?
Au départ, une conjecture de Hilbert : Il existe un algorithme universel capable de résoudre tout problème mathématique qu'on lui poserait, c'est-à-dire capable de déterminer, pour n'importe quelle proposition mathématique, si elle est vraie ou fausse. Et Hilbert propose un programme de recherche particulièrement dense pour parvenir à la formulation de cet algorithme.

Turing aborde la question un peu autrement : Existe-t-il un algorithme capable de calculer la décidabilité d'une proposition mathématique ? (je ne suis pas sûr de bien voir la différence, d'ailleurs)
Pour y réponde, Turing commence par formaliser la notion d'"algorithme" : Une suite d'instructions est un algorithme ssi elle peut être retranscrite sur le ruban d'une machine de Turing universelle (en somme).
Ceci fait, Turing propose : L'algorithme de Hilbert doit être un algorithme d'une machine de Turing universelle capable, quelle que soit la conjecture mathématique qu'on lui présente, de s'arrêter sur 0 ou 1, c'est-à-dire de déterminer s'il existe une preuve en faveur de cette conjecture, ou non. En effet, si on présente d'un côté une conjecture, et de l'autre les preuves simples de cette conjecture, l'algorithme pourra décider si l'une de ces preuves est juste. Si aucune ne l'est, il pourra passer aux preuves moins simples. Et ainsi de suite, jusqu'à finir par trouver une preuve juste. Ce qui signifie que s'il n'existe aucune preuve de la conjecture, l'algorithme continuerait à tourner indéfiniment.
Turing eut l'idée de se demander s'il existait un (autre) algorithme universel capable de déterminer si un algorithme "termine" ou non. C'est le problème de "l'arrêt", dont il montre qu'il est équivalent au problème de la décision, et conclut à la négative.
Par conséquent, le problème de la décision dépasse l'algorithmie, et n'a pas (à ce jour) de solution.

Du reste, le lendemain même de la présentation de Hilbert (je crois), Gödel présente son premier théorème d'incomplétude : Toute théorie mathématique contient des vérités indémontrables, qui n'admettent pas de preuve et/ou qui ne sont pas réfutables. Ces théories sont dites "indécidables". Et par la suite, Gödel démontrera, second théorème, qu'il en sera toujours ainsi.

Qu'est-ce que la complexité d'un algorithme ?
Soit, donc, un problème mathématique, la question qui se pose est : Existe-t-il un algorithme capable de solutionner ce problème, ou de décider qu'il n'y a pas de solution, et ce, dans une durée... comment dire, raisonnable ? (je ne sais même pas trop comment formuler le problème, en fait).
Par exemple, il existe un algorithme relativement simple pour solutionner le problème des échecs, càd gagner à tous les coups quelle que soit la stratégie adverse. Mais c'est un algorithme qui, à chaque coup de l'adversaire, devrait jouer toutes les parties possibles afin de déterminer la stratégie gagnante -autrement dit, un algorithme qui prendrait énormément de temps à tourner avant de jouer. Apparemment, et si je comprends bien, le calcul du nombre d'états possibles est une fonction exponentielle.
Par exemple, tu as choisi l'exemple du sudoku, AS, je comprends maintenant pourquoi : Le nombre de remplissages possibles de la grille (de 9 cases sur 9) est (9x9)^9 soit approx. 10^17.  

Donc, un problème pour lequel il est possible de réaliser un algorithme capable de solutionner ce problème ou de décider qu'il n'y a pas de solution dans un temps... raisonnable est dit de complexité "polynomiale" (ou "facile"). Un problème pour lequel ce n'est pas possible est dit "non-polynomial" (ou "difficile").

Non, il y a un truc que je ne comprends pas entre "P/NP" et "facile/difficile".
Et je bute aussi, pour l'instant, sur la notion de temps que j'ai appelé "raisonnable" : Il y a une limite claire entre P et NP ?

[AntiSubjectiviste]

Qu'est-ce qu'une machine de Turing ?
Une machine de Turing est un modèle théorique, idéal et simplifié, d'ordinateur programmé pour exécuter une certaine tâche. Sa table de transition indique ce qu'elle doit faire à chaque étape. L'intérêt du concept de machine de Turing est que l'on considère que tout algorithme (au sens intuitif du terme) peut-être traduit sous la forme d'une machine de Turing avec une table de transition appropriée. Autrement dit, on considère que l'on peut confondre "machine de Turing" et "algorithme" : c'est ce qu'affirme la thèse de Church-Turing, qui explique pourquoi on invoque les machines de Turing dès que l'on s'intéresse aux algorithmes.

Lorsqu'un problème est théoriquement résoluble sur une machine de Turing, cela signifie donc qu'il est algorithmiquement résoluble tout court, et donc qu'il l'est sur tout autre type d'ordinateur ou de machine (ce qui est une conséquence hyper puissante).

Il est vrai qu'il existe une machine de Turing "universelle", dont la table de transition permet de simuler toutes les machines de Turing possibles. Cette machine de Turing universelle est donc une sorte de fusion de toutes les machines en une seule, un super-émulateur. Mais c'est un autre sujet, qui n'est pas nécessaire pour comprendre la conjecture P=NP.

Par contre, la notion de machine de Turing non-déterministe est importante. Une machine de Turing "normale" (ou déterministe) passe, à chaque étape, d'un état à un seul autre état, en partant d'un état initial pour aboutir à un unique état final. L'ensemble de tous ses états intermédiaires se succèdent linéairement dans le temps, comme les maillons d'une chaîne. Une machine de Turing non-déterministe, par contre, peut passer d'un état à plusieurs autres états en parallèle, et ce à chaque étape de son exécution. C'est comme si une telle machine pouvait explorer différentes pistes simultanément. L'ensemble de ses états intermédiaires ne se succèdent pas linéairement, mais sous la forme d'un arbre de décision dont les branches se démultiplient constamment.

Il faut noter que les machines de Turing déterministes sont réalistes (et correspondent à nos ordinateurs réels). Les machines non-déterministes, par contre, sont des fictions théoriques : aucun ordinateur actuel ne fonctionne de façon non-déterministe.

Qu'est-ce qu'un problème de décision ?
(Ne pas confondre la notion de problème de décision avec ce qu'on appelle LE problème de l'arrêt (the halting problem, ou le problème de déterminer algorithmiquement si un algorithme va s'arrêter ou boucler indéfiniment). Ce dernier est intéressant en soi, mais n'est pas directement lié à la question P=NP. Ce qui suit développe la notion de problème de décision.)

Un problème de décision est simplement une question dont la réponse est oui/non. Un problème de décision est (algorithmiquement) résoluble s'il existe un algorithme qui aboutit à une réponse ("oui" ou "non"). En général, on s'intéresse aux problèmes portant sur un nombre donné en input. Exemple : "le nombre X est-il pair ?" où X est fourni par l'utilisateur. Voici un algorithme basique pour le résoudre :

1. Demander à l'utilisateur d'entrer la valeur de X.
   
2. Si le dernier chiffre de X est "0", "2", "4", "6" ou "8", alors répondre "oui", sinon, répondre "non".
   

Cet algorithme est ici présenté intuitivement, mais il est facile de le coder concrètement dans n'importe que langage de programmation, et théoriquement sous la forme d'une machine de Turing. Le problème de décider si un nombre donné est pair ou pas est donc algorithmiquement résoluble.

Dans cet exemple, on remarque même que même si X est un nombre très grand, l'algorithme n'examine que son dernier chiffre. La réponse sera donc toujours donné en une seule étape (la 2), et le temps d'exécution ne va même pas s'allonger même si la valeur de X augmente. On dira que cet algorithme est de complexité constante : son temps d'exécution est constant, peu importe la taille de l'input.

Qu'est-ce que la complexité d'un algorithme ?
Mais en général, le temps d'exécution augmente quand la taille de l'input augmente. Voici un autre problème de décision élémentaire : "le nombre X est-il premier ?" Voici un algorithme basique pour le résoudre :

1. Demander à l'utilisateur d'entrer la valeur de X.
   
2. Pour chaque nombre D entre 2 et X-1 :
   
   1. Diviser X par D.
      
   2. Si le résultat est un nombre entier, répondre "non" et s'arrêter. Sinon, continuer.
      
   
   
   
3. Répondre "oui" et s'arrêter.
   

Cet algorithme examine si X possède un diviseur autre que 1 et lui-même; si oui, alors X n'est pas premier (réponse "non"), sinon il est premier (réponse "oui"). Ici, plus X est élevé, plus l'algorithme va devoir le diviser par les nombres qui lui sont inférieurs. Le temps d'exécution va donc augmenter avec la taille de l'input X.

La question est savoir comment le temps d'exécution augmente quand la taille de l'input augmente : augmente-t-il un peu, beaucoup, à la folie ? C'est là qu'interviennent les mathématiques : si la taille de l'input est notée n, alors le temps d'exécution sur une certaine machine de Turing (déterministe ou pas) est une fonction de n. Si cette fonction est polynomiale en n (par exemple, 2n+1, n², n³, ...), alors on dira que l'algorithme est de complexité polynomiale (sur cette machine de Turing). Si, par contre, cette fonction n'est pas polynomiale en n (par exemple, 2ⁿ, qui est une exponentielle en n), alors on dira que l'algorithme n'est pas de complexité polynomiale (sur cette machine de Turing).

Le point est que si le temps d'exécution est exponentiel en n (ce qui n'est pas polynomial en n), alors il devient vite déraisonnablement long lorsque la taille n de l'input augmente. Les algorithmes de sécurité informatique reposent là-dessus : les clés de cryptage peuvent théoriquement être crackées, mais ces clés sont des codes suffisamment longs pour que le temps de crackage soit, en pratique, déraisonnablement long pour un pirate (des millions d'années, même sur un ordinateur performant).

Enfin, lorsqu'un problème de décision est résoluble par un algorithme de complexité polynomiale sur une machine de Turing déterministe, alors on dit que ce problème est de classe P.

Avant de parler de la classe NP, il faut d'abord définir ce qu'est un problème de décision "vérifiable" (ce qui est moins exigeant que "résoluble"). Un problème de décision (portant sur un input X) est (algorithmiquement) vérifiable s'il existe un algorithme (sur une machine de Turing) qui détecte les valeurs de X qui entraînent la réponse "oui".

Pour parler de la classe NP, il faut faire intervenir les machines de Turing non-déterministes. Une machine de Turing non-déterministe est plus puissante qu'une version déterministe : elle est capable d'effectuer en parallèle plusieurs chaînes d'instructions, sans limite. (Rappelons toutefois que ces machines sont des fictions théoriques irréalisables en pratique.) Il y a toutefois un lien entre les deux : un problème résoluble en temps polynomial sur une machine non-déterministe, est vérifiable en temps polynomial sur une machine déterministe (et ça, c'est accessible via nos ordinateurs). De tels problèmes sont, par définition, de classe NP. La différence entre les classes P et NP est donc celle entre les notions de "résoluble" et de "vérifiable" (tous deux en temps polynomial).

Beaucoup de problèmes importants sont de classe NP. Par exemple : le problème de cracker un mot de passe. Si l'on possède le bon mot de passe, il est facile de vérifier que c'est le bon. Par contre, il est très difficile de trouver, à partir de rien, le bon mot de passe : si le mot de passe est long et complexe, il faudrait, dans l'état de nos connaissances, un temps déraisonnablement long pour le cracker.

Une des grandes questions du siècle est de savoir si P=NP, c'est-à-dire si les problèmes NP (vérifiables en temps polynomial) sont également P (résolubles en temps polynomial). Si oui, ça serait terrible : cela signifierait qu'il existe un algorithme de complexité polynomiale (donc, relativement "rapide") pour cracker n'importe quel mot de passe ou clé de cryptage ! Mais la communauté scientifique estime en majorité que P et NP sont différents, heureusement... même si on ne l'a pas encore prouvé.

[Bergame]

Merci AS !

Lorsqu'un problème est théoriquement résoluble sur une machine de Turing, cela signifie donc qu'il est algorithmiquement résoluble tout court, et donc qu'il l'est sur tout autre type d'ordinateur ou de machine -ce qui est une conséquence hyper puissante.

Oui, et d'autant plus parce que, si je comprends bien, toutes les opérations mathématiques peuvent être formalisées par un algorithme. Dire qu'un problème est théoriquement résoluble sur une machine de Turing revient donc à dire qu'il est résoluble mathématiquement (?)

Par contre, la notion de machine de Turing non-déterministe est importante. Une machine de Turing "normale" (ou déterministe) passe, à chaque étape, d'un état à un seul autre état, en partant d'un état initial pour aboutir à un unique état final. L'ensemble de tous ses états intermédiaires se succèdent linéairement dans le temps, comme les maillons d'une chaîne. Une machine de Turing non-déterministe, par contre, peut passer d'un état à plusieurs autres états en parallèle, et ce à chaque étape de son exécution. C'est comme si une telle machine pouvait explorer différentes pistes simultanément. L'ensemble de ses états intermédiaires ne se succèdent pas linéairement, mais sous la forme d'un arbre de décision dont les branches se démultiplient constamment.

Ok...
Si théoriquement c'est possible, est-ce que cela n'implique pas un principe de pondération de la donnée en entrée ?
(je fais l'analogie avec ce que je comprends des réseaux de neurones formels, mais ça ne doit pas être ça... )

Qu'est-ce qu'un problème de décision ?
Etc.

Ok, très clair !

Qu'est-ce que la complexité d'un algorithme ?
[...]
La question est savoir comment le temps d'exécution augmente quand la taille de l'input augmente : augmente-t-il un peu, beaucoup, à la folie ? C'est là qu'interviennent les mathématiques : si la taille de l'input est notée n, alors le temps d'exécution sur une certaine machine de Turing (déterministe ou pas) est une fonction de n. Si cette fonction est polynomiale en n (par exemple, 2n+1, n², n³, ...), alors on dira que l'algorithme est de complexité polynomiale (sur cette machine de Turing). Si, par contre, cette fonction n'est pas polynomiale en n (par exemple, 2ⁿ, qui est une exponentielle en n), alors on dira que l'algorithme n'est pas de complexité polynomiale (sur cette machine de Turing).

Ok ! Voila donc ma "limite".
Au passage, j'apprends qu'il y a une balise BBCode pour écrire les exposants.

Bon, je pense que je comprends pas trop mal, jusqu'à ce que tu abordes NP. Là, je suis largué.

Je tente un truc. Quand tu dis :

Avant de parler de la classe NP, il faut d'abord définir ce qu'est un problème de décision "vérifiable" (ce qui est moins exigeant que "résoluble"). Un problème de décision (portant sur un input X) est (algorithmiquement) vérifiable s'il existe un algorithme (sur une machine de Turing) qui détecte les valeurs de X qui entraînent la réponse "oui".

... est-ce que cette distinction vérifiable / résoluble est la même que celle entre la conjecture de Hilbert et sa reformulation par Turing (que je ne comprenais pas bien) ? :

Au départ, une conjecture de Hilbert : Il existe un algorithme universel capable de résoudre tout problème mathématique qu'on lui poserait, c'est-à-dire capable de déterminer, pour n'importe quelle proposition mathématique, si elle est vraie ou fausse.
Turing aborde la question un peu autrement : Existe-t-il un algorithme capable de calculer la décidabilité d'une proposition mathématique ? (je ne suis pas sûr de bien voir la différence, d'ailleurs)

un problème résoluble en temps polynomial sur une machine non-déterministe, est vérifiable en temps polynomial sur une machine déterministe (et ça, c'est accessible via nos ordinateurs). De tels problèmes sont, par définition, de classe NP. La différence entre les classes P et NP est donc celle entre les notions de "résoluble" et de "vérifiable" (tous deux en temps polynomial).

Je tente de comprendre.
Le "problème" spécifique d'une machine non-déterministe n'est pas tant la taille de l'input n que le nombre d'états internes, démultiplié. L'idée en est que si on était capable de construire une machine de Turing non-déterministe, elle serait capable de traiter un même échantillon n plus rapidement qu'une machine déterministe, càd elle serait capable de résoudre un même problème plus rapidement.

Non, ça ne doit pas être ça. Je ne vois pas le lien avec ton exemple du mot de passe :

Beaucoup de problèmes importants sont de classe NP. Par exemple : le problème de cracker un mot de passe. Si l'on possède le bon mot de passe, il est facile de vérifier que c'est le bon. Par contre, il est très difficile de trouver, à partir de rien, le bon mot de passe : si le mot de passe est long et complexe, il faudrait, dans l'état de nos connaissances, un temps déraisonnablement long pour le cracker.

D'accord, mais ça, c'est le même exemple que le sudoku ? A raison d'un mot de passe très simple à 8 lettres, on a déjà, euh, (8x26)⁸ combinaisons possibles, si je ne me trompe ? Donc ok, on a là un problème de complexité non-polynomiale, càd de classe NP (?) Mais, en somme, qu'est-ce qu'ajoute au raisonnement la machine non-déterministe ?

[Saint-Ex]

.

À Bergame et AntiSubjectiviste :

Bien que je ne participe pas à votre discussion (en fait, j'en serais incapable), sachez que je la suis avec un intérêt que je serais incapable de dissimuler.

Voilà qui me plait par la matérialité absolue qui s'en dégage absolument. C'est dans ce genre de matérialité que je vois le développement intelligent de l'intelligence. (N'allez pas confondre mon enthousiasme avec quelque flatterie, sinon je ne vous parle plus !)

Je vais vous relire attentivement, tiens !

.

[AntiSubjectiviste]

Oui, et d'autant plus parce que, si je comprends bien, toutes les opérations mathématiques peuvent être formalisées par un algorithme. Dire qu'un problème est théoriquement résoluble sur une machine de Turing revient donc à dire qu'il est résoluble mathématiquement (?)

En gros, oui. Plus précisément (et ce n'est pas évident du tout, donc c'est extraordinaire), il y a une correspondance entre les algorithmes informatiques et les démonstrations mathématiques : tout théorème mathématique (vu comme la conclusion d'une démonstration, donc d'une suite de propositions) peut être traduit en un algorithme sur une machine de Turing, et vice versa. C'est la correspondance de Curry-Howard. C'est pour cette raison que l'incomplétude de Gödel portant sur un système axiomatique correspond à un certain phénomène portant sur les algorithmes (l'indécidabilité du problème de l'arrêt).

Bon, je pense que je comprends pas trop mal, jusqu'à ce que tu abordes NP. Là, je suis largué.

Ce n'est quand-même pas évident si tu découvres le domaine. Il y a beaucoup de notions subtiles, impossibles à comprendre sur base des définitions seules. Il faut bosser des exemples, faire des exercices, prendre le temps de réfléchir, pour comprendre ces notions.

... est-ce que cette distinction vérifiable / résoluble est la même que celle entre la conjecture de Hilbert et sa reformulation par Turing (que je ne comprenais pas bien) ?

Non, ça n'a rien à voir à la base (même si on peut toujours faire des liens).

Mais, en somme, qu'est-ce qu'ajoute au raisonnement la machine non-déterministe ?

Pour simplifier, une machine non-déterministe peut traiter en temps polynomial des problèmes qui, sur une machine déterministe, sont traités en temps exponentiel. Ou plus simplement encore : une machine non-déterministe traite sous la forme d'un seul cas de figure un problème qui, sur une machine déterministe, doit se décomposer en plusieurs cas de figure.

Une machine non-déterministe fonctionne comme une armée de machines déterministes travaillant simultanément, chacune chargée de développer un cas de figure.

[Contenu sponsorisé]