P=NP question :

[djhdoi1]

Bonjour,

Résolvons nous le problème du millénaire si l'on parvient à montrer qu'une solution en temps polynomiale à l'un de ces problèmes n'existe pas ?
Autrement dit (et je saute peut être une étape) : P différent de NP...
Cordialement,
-----

[djhdoi1]

Bonjour,

Résolvons nous le problème du millénaire si l'on parvient à montrer qu'une solution en temps polynomiale à l'un de ces problèmes NP n'existe pas ?
Autrement dit il n'existe pas d'algo NP résolvant le problème.....
Cordialement,

[Deedee81]

Salut,

Résolvons nous le problème du millénaire si l'on parvient à montrer qu'une solution en temps polynomiale à l'un de ces problèmes NP n'existe pas ?

Ben oui, c'est le but. Mais c'est loin d'être simple à démontrer.

[Superbenji]

Bonjour,
Et même si on démontrait qu'un tel algorithme existe, ça ne veut pas forcément dire qu'on pourrais le trouver, ou qu'il serais utilisable en pratique. Ou bien P=NP pourrais aussi être indécidable dans les théories usuelles.

[A voir en vidéo sur Futura]

[amineyasmine]

Bonjour,

Résolvons nous le problème du millénaire si l'on parvient à montrer qu'une solution en temps polynomiale à l'un de ces problèmes n'existe pas ?
Autrement dit (et je saute peut être une étape) : P différent de NP...
Cordialement,

Bonjour
P=NP est une question qui vous demande est ce que P=NP ou est-ce P est différent NP ?
Je pense que tu as compris.

Je relance, mais dans une autre direction.

Le problème P vs NP n’est pas un problème mathématique, c’est bizarre cette erreur de nomination.

Mathématiques, un problème : soit il est P, soit il est NP,

La question posée est : est-ce que le problème NP est en réalité est P, donc il n’était pas NP mais depuis qu’il existe, il est P.

Cette question je ne la qualifie pas mathématique ….. D’après ce que je comprends de mathématique

[jacknicklaus]

La question posée est : est-ce que le problème NP est en réalité est P, donc il n’était pas NP mais depuis qu’il existe, il est P.

pas du tout. car P et NP parlent de 2 choses différentes. P parle de résolution, NP parle de vérification.
Il est clair que si l'on sait résoudre (en temps raisonnable, ce qui est "P") alors on sait vérifier (en temps raisonnable, ce qui est "NP")
P ==> NP

la question ouverte porte sur la réciproque.
NP ==> P ??

[pm42]

Le problème P vs NP n’est pas un problème mathématique, c’est bizarre cette erreur de nomination.
...
D’après ce que je comprends de mathématique

Il n'y a pas d'erreur de nomination. Le problème est la dernière phrase de ton post.

Mathématiques, un problème : soit il est P, soit il est NP

Absolument pas : il existe de nombreuses classes de problèmes, P et NP ne sont que 2 d'entre elles : https://fr.wikipedia.org/wiki/Classe_de_complexité

La question posée est : est-ce que le problème NP est en réalité est P, donc il n’était pas NP mais depuis qu’il existe, il est P.

Je me demande ce que cela peut bien vouloir dire.

[amineyasmine]

La question posée est : est-ce que le problème NP est en réalité est P, donc il n’était pas NP mais depuis qu’il existe, il est P.

Je me demande ce que cela peut bien vouloir dire.

Bonjour

Cela veut dire qu’il existe des problèmes NP dont la résolution nécessite une succession d’opérations mathématiques dont le degré n’est polynomial (exponentiel) mais leurs vérifications à petit nombre à un ordre polynomial (x^n).

La question : Ces problèmes, particuliers, sont en réalité des problème P, c.-à-d. que leurs résolution nécessite une succession d’opérations mathématiques dont le degré est polynomial (x^n).

D’où vient la question : si on arrive à les vérifier (polynomialement) on finira par les résoudre définitivement (polynomialement)

[pm42]

Cela veut dire qu’il existe des problèmes NP dont la résolution nécessite une succession d’opérations mathématiques dont le degré n’est polynomial (exponentiel) mais leurs vérifications à petit nombre à un ordre polynomial (x^n).

Résolution non polynomiale mais vérification polynomiale, c'est la définition même de NP.

Ces problèmes, particuliers, sont en réalité des problème P, c.-à-d. que leurs résolution nécessite une succession d’opérations mathématiques dont le degré est polynomial (x^n).

Ce ne sont pas des problème particuliers. Et tu viens de dire le contraire de la phrase d'au dessus sur leur résolution.

D’où vient la question : si on arrive à les vérifier (polynomialement) on finira par les résoudre définitivement (polynomialement)

Oui, c'est le fameux problème P=NP sur lequel on ne sait pas grand chose.

Soit la façon dont tu exprimes les choses est assez peu claire et il faudrait être plus précis soit tu devrais vérifier que tu utilises bien les bonnes définitions.

[amineyasmine]

Résolution non polynomiale mais vérification polynomiale, c'est la définition même de NP.

NP = Résolution non polynomiale (avec vérification x ou autre chose ) ca reste non polynomiale
P = Résolution polynomiale et aussi, bien sûr, vérification polynomial, ou peut être vérification linéaire

mathématiquement P et NP son bien définis et on est en mathématique

maintenant NP, est ce qu'il n'est pas par Hazard P ? c'est cette question que je trouve non mathématique

[pm42]

NP = Résolution non polynomiale (avec vérification x ou autre chose ) ca reste non polynomiale

Non, fait l'effort de lire la définition : https://fr.wikipedia.org/wiki/NP_(complexité)

Parce que là, c'est carrément limite de venir parler "d'erreur de nomination" quand tu ne sais même pas de quoi tu parles.

[amineyasmine]

Non, fait l'effort de lire la définition : https://fr.wikipedia.org/wiki/NP_(complexité)

Parce que là, c'est carrément limite de venir parler "d'erreur de nomination" quand tu ne sais même pas de quoi tu parles.

bonjour

ok
j'ai lu et j'ai noté : L'un des grands problèmes ouverts de l'informatique théorique

ce domaine je ne le connais pas

est ce que c'est mathématiques ?

[gg0]

Oui, c'est des mathématiques.
Et c'est de l'informatique, puisque ça concerne les algorithmes.

Cordialement.

[amineyasmine]

oui, c'est des mathématiques.
Et c'est de l'informatique, puisque ça concerne les algorithmes.

Cordialement.

bonjour
moi, je ne sais pas
mais @Médiat, surement ne sera pas d'accord; les maths sont plus précis que cela

il fallait poster en logique

[jacknicklaus]

moi, je ne sais pas

En effet. On avait remarqué aussi.

les maths sont plus précis que cela
il fallait poster en logique

Là tu t'enfonces. A ta place ,j'éviterais.

[pm42]

Là tu t'enfonces. A ta place ,j'éviterais.

Je trouve aussi et ce n'est pas gentil de prendre le risque de gacher la soirée de Noël de Mediat si jamais il voyait qu'on raconte n'importe quoi sous son nom et surtout qui.
C'est beau de ne pas savoir ce que sont les maths, l'informatique théorique et la logique mais d'expliquer quand même.

[Médiat]

Je trouve aussi et ce n'est pas gentil de prendre le risque de gacher la soirée de Noël de Mediat si jamais il voyait qu'on raconte n'importe quoi sous son nom et surtout qui.

Moi qui croyait que c'était mon cadeau de Noël

[pm42]

Moi qui croyait que c'était mon cadeau de Noël

Quand je pense qu'en informatique théorique, on se bouffe de la théorie des catégories avec monoides et tout ça, que cela a été fondé par Von Neumann et Turing qui se débrouillaient en maths et qu'il faut lire que ce n'est pas précis
Bon, je vais aller attaquer le foie gras, ça va faire passer.

[amineyasmine]

Moi qui croyait que c'était mon cadeau de Noël

joyau noël médiat

c'est juste des dires innocents

[Médiat]

Bon, je vais aller attaquer le foie gras, ça va faire passer.

Je te souhaite un bon Suduiraut

[pm42]

Je te souhaite un bon Suduiraut

Je suis plutôt Yquem 89 ou 90 mais c'est un sujet de conflit dans le couple donc on va faire des compromis.

Joyeux Noël

[amineyasmine]

bonjour
joyau noël à tous

les maths et l'informatique ont de l'avenir ensembles

[Médiat]

Je suis plutôt Yquem 89 ou 90 mais c'est un sujet de conflit dans le couple donc on va faire des compromis.

Mon dernier Yquem était de 55 (un cadeau), mais je pleure à chaque fois que j'y pense, alors j'évite le sujet


Joyeux Noël

[pm42]

Mon dernier Yquem était de 55 (un cadeau), mais je pleure à chaque fois que j'y pense, alors j'évite le sujet

Oui, c'est du bonbon liquide en mieux.

[Liet Kynes]

Quand je pense qu'en informatique théorique, on se bouffe de la théorie des catégories avec monoides et tout ça, que cela a été fondé par Von Neumann et Turing qui se débrouillaient en maths et qu'il faut lire que ce n'est pas précis
Bon, je vais aller attaquer le foie gras, ça va faire passer.

Allez histoire de faire passer l'idée.. petit cadeau de dessous le sapin (c'est un arbre avec des branches des noeuds des feuilles donc il est logique); une déco de Noël "Von Neuman.."

[invite7339e54b]

Bonsoir @amineyasmine,

Il y a un lien, étant donné que il y a de l'Analyse Numérique qui s'intéresse aux complexités des algorithmes

[amineyasmine]

Bonsoir @amineyasmine,

Il y a un lien, étant donné que il y a de l'Analyse Numérique qui s'intéresse aux complexités des algorithmes

oui c'est vrai

[pm42]

les maths et l'informatique ont de l'avenir ensembles

Il y a un lien, étant donné que il y a de l'Analyse Numérique qui s'intéresse aux complexités des algorithmes

Je suppose que le lambda calcul, les fonctions récursives partielles, la machine de Turing, les codes correcteurs d'erreurs, les fonctions à sens unique et les courbes elliptiques pour la signature/cryptage, les grammaires non contextuelles de Chomsky, le lemme d'Ogden, l'algèbre relationnelle, la catégorie de Kleisli, la démonstration du théorème des 4 couleurs vous sont inconnus ?
Et on pourrait continuer longtemps, parler de la théorie des graphes, des fondements de l'IA et de l'utilisation des statistiques bayésiennes.

Je suggèrerai bien de lire au moins la page Wikipedia sur l'informatique théorique mais c'est apparemment en pure perte même en ce jour de Noël, j'ai eu envie de croire à un miracle avant de faire la vaisselle d'hier soir

[Médiat]

Bonjour,

...

Et que dire de Coq(par exemple) et de la correspondance de Curry-Howard ?

[pm42]

Et que dire de Coq(par exemple) et de la correspondance de Curry-Howard ?

Je m'étais dit que si on arrivait jusqu'au théorème des 4 couleurs, on allait passer à Coq et de Kleisli, on découvrait la programmation fonctionnelle et de là, la technique du currying qui elle même ouvrait des portes.
Non, je blague et sincèrement, on reste sur un forum de vulgarisation mais tu as raison : il reste encore beaucoup de choses.
La théorie des types aussi est intéressante.