P!=NP ?

Il semblerait que le résultat annoncé soit P $\neq$ NP

Ce qui ne m'empêchera pas de planter mes salades.

amicalement

e.v.

Si vraiment il a raison je trouve ça dommage : j'eusse grandement préféré que ces deux classes coïncidassent, c'eût été nettement plus esthétique à mon sens (et trois verbes au subjonctif imparfait dans la même phrase, vlan !).

Oui, Guego et donc ce sont les auxiliaires (qui sont aussi des verbes !) qui sont au subjonctif imparfait.

Je suis bien d'accord ! J'aurais peut-être dû dire que le subjonctif imparfait était présent trois fois dans ma phrase (une fois pour le verbe "coïncider", et deux fois pour l'auxiliaire "avoir").

C'est pourtant simple : le conditionnel passé deuxième forme d'un verbe donné se forme en conjuguant l'auxiliaire (avoir ou être) au subjonctif imparfait et en lui adjoignant le participe passé dudit verbe.

Jeune que je suis, j'ai l'impression de vivre l'effervescence qu'on a pu connaître lors de l'annonce de la preuve du théorème de Wiles ou de la conjecture de Poincaré (théorème de Perelman ? ).

Jeune que je suis, j'ai l'impression de vivre l'effervescence qu'on a pu connaître lors de l'annonce de la preuve du théorème de Wiles ou de la conjecture de Poincaré (théorème de Perelman ? ).

De quelle efferevescence parles-tu?? De la subite empoignade de GG et Sylvain sur l'imparfait du subjonctif (en tout cas bravo pour la tentative, Sylvain... )

Concernant le résultat, j'espère qu'il sera traduit en français, j'ai parcouru le résumé anglais, bof bof, je ne capte pas grand-chose malgré la présence d'un "synopsis".

C'est un peu dommage cette "compétition" qui conduit certains chercheurs à ne pas simplifier avant publication (je comprends la nécessité de la prise de date évidememnt), mais maintenant, on va devoir rester en haleine, le temps qu'un texte qui tienne la route soit présenté au public.

Pour Wiles et Poincaré encore, je peux comprendre que ça n'ait pas été fait (vue la nature calculatoire des énoncés), mais là, loool y a intérêt à ce qu'il y ait un vrai synopsis peaufiné qui soit construit pour le reste des spectateurs!!!! :X

en fait, c'est "il existe une classe NP de problèmes " pas "un" problème (c'est un abus de langage usuel)

Bin pour te répondre "oui": par exemple, si on admet un nombre infini d'états pour les machines de Turing, on peut même construire un automate fini qui résout tout (classe de) problème en temps linéaire

Mais toute la question est: "est-ce honnête?"

oui, mais Penrose (ce qui n'entache pas son incroyable inspiration et son investissement, je lui dois presque tout d'ailleurs en ce qui concerne la MQ) s'est trompé dans son approche du problème.

En fait, précisément, il nie la thèse de Church et a plus ou moins prétendu expliquer pourquoi dans "les ombres de l'esprit" (livre que je recommande à tous).

Il a le mérite d'être clair et d'entrer dans les détails.

Mais il postule (ça fait partie de ses axiomes) qu'il y a un ensemble E de vérités mathématiques sûres auquel le cerveau humain a ou aura accès au bout d'un certain temps, ensemble d'énoncés qui ne serait pas récursivement énumérable (par le théorème de Godel).

C'est vrai que son H==>sa conclusion est correct, mais hélas, nonH. (Alors qu'il croit à H et croit ça partagé même par les spécialistes au fond d'eux.

En fait, l'enseignement qu'a initié le th de godel est en gros très simple: il y a des degrés de certitudes. Par exemple la consistance de Peano est "un peu moins sûr" que l'infinité des nb premiers, etc, etc. Quanf on approche de la consistance de ZF, on est déjà en terrain nettement moins sûr, etc, etc. C'est très "continu".

Penrose nie ça farouchement! Il s'est construit une sorte de foi platonicienne qui va jusqu'à "fixer" le E ci-dessus (et en croyant à son E, évidemment, il le croit non récursivement énumérable, mais ça c'est pas le côté "dur" de la découverte de Godel)

Comme il connait bien la MQ, il cherche d'ailleurs dans plusieurs directions et voudrait aussi trouver dans la MQ de quoi peut-être "expliquer E", du moins son accessibilité à l'humain en même temps que sa non rec enumérabilité.

Il est allé jusqu'à enquêter auprès des biologistes pour trouver les "microtubules" des petits constituants du cerveau qui seraient quantiques.

Mais encore une fois, sa position de "foi" (de très grande conviction du moins) le conduit à des erreurs inévitables quand on "veut" absolument quelque chose. En MQ, par exemple, il a décidé de nier les MP et du coup est entrain de se taper la tête contre les murs. Mais il se la tape tellement bien qu'il a proposé une expérience, presque simple, dont il pronostique un résultat contraire à ce que la MQ prévoit, dans laquelle la gravité "réduit" la fonction d'onde (selon l'expression consacrée). Ca aura le mérite d'être tranchée probablement dans un avenir pas si lointain.

C'est un homme remarquable car pour partager tout ça, il n'est pas avare de son temps et de ses efforts: il a écrit trois livres inoubliables où il essaie de tout reprendre à la base pour soumettre ses arguments jusqu'à l'homme de la rue. Je te recommande ces trois livres: "l'ordinateur, l'esprit et les lois de la physique" repris presque entièrement par "les ombres de l'esprit" et son dernier (que j'ai, le seul) "les lois de l'univers".

Pour te répondre, sinon, ce serait malhonnête car ça déplacerait le problème: un nombre infini d'états, est un ensemble quelconque d'états acceptants, autant dire que c'est donner gratuitement une solution à chaque problème. C'est déjà pas mal et notable d'avoir ce protocole turinguien très simple (un nombre fini d'états et de transitions) qui va si loin que personne n'a ne serait-ce qu'égratigner la thèse de Church à ce jour.

Bonjour à tous,
Je profite de ce fil et des interventions de Sylvain et ccnc pour poser une question qui me préoccupe depuis longtemps à propos de P=NP.

Quelqu'un connait-il des exemples de phénomènes naturels - ou de dispositifs physiques artificiels - dont les évolutions ne peuvent être prédites que par la résolution de problème NP-Complet (typiquement je pense par exemple à un phénomène ayant un état initial instable qui évoluerait vers un état stable tel que ce dernier nécessite la résolution d'un problème NPC pour être prédit à l'avance).

Le cas échéant peut-on considérer que ces phénomènes/dispositifs "résolvent" des problèmes NPC ?
Dans quelle mesure des phénomènes continus peuvent-ils être discrétisés et pris en compte comme exemples de phénomènes résolvant des problèmes NPC ?

Quels temps (exponentiel, polynomial?) prennent ces phénomènes pour parvenir à l'état prédit en fonction de l'état initial?

Si vous ne savez pas, sauriez vous où trouver des informations sur ce sujet? (J'ai lu l'Esprit, l'ordinateur et les lois de la physique de Roger Penrose)

PS: ne me répondez pas "un exemple de dispositifs physique est un écran affichant les solutions d'un problème NPC résolu par ordinateur . La prédiction de l'évolution de l'affichage de l'écran est un problème NPC". Seuls les dispositifs ne pouvant pas être ramenés de manière évidente à une machine de Turing ont un intêret.

je crois que du savon répandu sur une toile d'araignée (artificielle et métallique) par exemple, ça marche, ça minimise une contrainte alors que le réussir sur le papier est NP complet (pas totalement sûr, mais il me semble que ça a été souvent affirmé)

Bin le problème sur les algorithmes quantiques (l'utilisation des mondes multiples si tu préfères) c'est que ceux connus (en tout cas de moi) ne résolvent pas des problèmes NP complets (en fait, le seul que je connaisse factorise les entiers et même si on ne sait pas le faire polynomialement de manière classiques, il n'est pas prouvé que c'est un problème non polynomial)

Tape "Shor informatique quantique" sur google

Quant aux autres magies quantiques, elles font carrément des trucs prouvés impossibles classiquement: les plus parlant sont l'algorithme de LovGrover et celui de D.Deutsch

Celui de Grover trouve un nombre compris entre 1 et n en posant racine carrée de n questions en moyenne (les questions sont obligées d'être de la forme "est-ce que c'est x?") (tape quantique Lov Grover sur google)

Celui de Deustch réussit à savoir si une fonction f à valeurs dans 2 est constante ou (on dit qu'elle est équilibrée) est telle que 0 a autant d'antécédents que 1 en ne calculant qu'une seule valeur (ie la "machinequantique" choisit un élément x et demande à la boite noire combien vaut f(x), puis donne sa réponse. Elle ne se trompe que si on lui ment à propos de f(x), ou si f n'est ni constante ni équilibrée

Je soupçonne par ailleurs que le principe deFermat (qui était un axiome et a été élucidé par la MQ) doit contenir des instances NP complète. (ie on s'amuse à dessiner plein de milieux différents, avec tout plein de vitesse de la lumière différentes pour chacun et faut trouver le chemin le plus rapide)

La façon dont s'y prennent les machines quantiques ci-dessus est descriptible d'une manière assez brutle et formelle: elles donnent l'illusion de ne poser qu'une seule question, mais elles en posent en fait suffisamment pour résoudre le problème en les répartissant dans les tranches du multimonde voisines.

Je suis septique, puisqu'on a atteint les limites de l'intelligence !

Marie

Visiblement ça semble sentir le sapin : voir la critique de la preuve

D'après le lien, Neil Immerman (one of the world’s experts on Finite Model Theory) semble émettre deux sérieuses réserves.

Merci pour l'information, bon bin, je ne dis même pas snif, parce quelque part, ça me plait de garder un espoir que P=NP (et même = PSPACE) éventuellement.

De toute façon, j'avais parcouru le synopsis, et je trouvais étonnant d'appeler à la rescousse autant de chapitres, dont des probabilités je crois?

Je ne prétends pas qu'il ne faut pas y faire appel pour trouver, mais je pense que le gars qui aurait trouvé après y avoir fait appel aurait presque immédiatement vue la nature du problème***ensuite la possibilité d'isoler le point clé purement "logique ou abstrait" et donc la version publiée ferait apparaitre une ligne de ce type (même si je sais que les gens se dépècheront de publier)

*** très général, hypergénéral même pourrait-on dire, il ne s'agit pas d'un énoncé extrémement pointu (de typ Fermat and co), et donc un progrès juste "de maths" ne me parait pas vraiment pouvoir permettre de prouver P$\neq $NP. Je pense que toute preuve (mais je peux complètement me tromper) nécessitera un argument (j'entends par là un lemme encore plus général que l'énoncé lui-même, du genre "invention du raisonnement par récurrence", etc) vraiment général

J'ai demandé à un ami logicien qui suit le dossier où ça en était.

Réponse : "La preuve a été entièrement démontée. Mais depuis, le mec a dit "j'ai tout patché et envoyé à un journal". Du coup, on sait pas où ça en est."

Selon la source Wikipédia :
1.Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement
une solution à un problème, implique de pouvoir la trouver rapidement ; ou encore, si ce
que nous pouvons trouver rapidement lorsque nous avons de la chance, peut être trouvé
aussi vite par un calcul intelligent.

Selon moi et sur une analyse conceptuelle épistémologique rapide, brouillon, et diffuse, orthographiquement pareil:

oui il faut pouvoir la trouver rapidement parce que sinon ca perd en valeur et pertinence.(réflexion-réfraction),
ca se diffuse et demande des moyens. La conservation d energie dans un referentiel inertiel, non inertiel (non biologique)
est selon moi une petite partie de la stucture de la theorie.

Temps la quantité ne peut faire la qualité, dans le sens ou on ne peut reproduire la qualité en quantité,
les 2 ayants des valeurs differentes. Si c est trop rapidement ca s apparente a de la chance.(perception fines)
le caclul est pas seulement mathématique mais biologique, cerebral, spatial, mecanique et ondulatoire.

Un champ de lumiere porte et traverse l information meme si on est pas la pour le voir,
"il y a les lieux connus qui ont plus besoin de lumiere pour etre distingués, perceptible
" il s agit d un phénomene de repetitions, de connaissances passé des lieux et de matiere-energie qui se dissipe,
le rapide est tres contrasté tandis tandis que le lent est moins pertinent car le contrastes affaiblit.

Tout depend de la nature du probleme a pouvoir resoudre, la cause, la fonction, il y a les problemes visibles d'autres
distinctif, sensoriel.

Un probleme est pas que visuel, et possede differente dimensions d ondes.

l oeil qui amene directement a la lumiere
le gout qui amene qu a nous.
l ouie qui fonctionne sur des frequence de courte distance et vitesse de deplacement
l odorat qui permet de sentir sur de tres courtes distances, des vitesses encore plus lente
besoin de vent.

Ne vont interesser ses valeurs que ceux qui sont en mesure de les recevoirs

Plus le probleme se dissipe de son rayon d action, engendre un transfert, une trainee,
qui s eloigne d 1 seul point de l obsevateur. ca depend quelle energie possede, degage et engendre
le probleme .

Je resoud pas le probleme meme si celui ci est factuellement possible.

Un probleme peut etre premedité, et donc en preparation et activé dans le futur,
dans ces cas il offre une perception plus grande, un meilleur contraste, emprunte.

En fait tout depend de la complexité du probleme. ou encore un probleme doit se resoudre dans une frequence similaire.
(on ne peut "biolologiquement organiquement" utiliser et lire un disque dur sans ses autres composants.)

1.on ne peut pas doper physiquement la machine musculairement ou mentalement.
2. la machine ne repond pas a la volonté de notre organisme

Un probleme c est une manoeuvre qui a une origine, c est une infraction, effraction, cumulation, detournement, dereglement, defaillance etc
Un probleme s enrichit et un probleme qui se condense qui possede son propre facteur de resolution.

C est presque aussi difficile que de vouloir observer notre systeme solaire
en entier, a l oeil nu, deja parce que le ciel est bleu une bonne partie du temps.
empechant une visualisation en tout points de l espace, sans compter les elements
nuageux, ou encore les lumieres des villes. et connaitre son fonctionnement general.

Il me semble qu on rentre et interagit dans des domaines de l ordre du photon, neutron..

le temps c est de la quantité,

un probleme peut avoir (initier, generer) et croiser differentes formes d interactions,

avec celui qui recherche la cause "premeditation" ou travail organisé,
ou par hasard de circonstance: de type perimetrique, "echographique", mais
sans memoire de reconnaissance du fait de cette fonction "hasardeuse",
celui ci est comme programmé dans 1 disque sans pouvoir restituer l information.

le probleme envoie un signal "electrique" et vibratoire qui se deploie par le mecanisme physique ,

et en théorie seul le signal peut resoudre le probleme.

c est comme un probleme plus il reste longtemps sur place plus
il obtient une charge de condensation, une empreinte, perceptibilité,
c est la duree, un probleme etant un arret. (c est sa resolution)

Un probleme qui ne pourrait etre resolu ou percu ne passe pas pour un probleme.

un probleme peut etre vu, imaginé, prévu, estimé, en direct,
un probleme etant souvent sous jacent, il est a l etat passif.
un probleme genere une radiation.

Le resultat est peut etre mathématique, mais il me semble qu ca s apparente
plus a de la physique, biologie, chimie, que de maths pur. P=NP pourtant c est court et concentré comme
equation

Philosophiquement et brièvement parlant:

La météorologie est une preuve de cette courte distance de prévision nécessaire du au mouvement,
si on ne la trouve pas rapidement, il est impossible d avoir la bonne solution.
A cela on reste dans 1 marge restreinte de possibilités.

on sait que l on va avoir un problème. Et en fait avec p=np on aimerait arriver à faire et trouver
les 365 jours du probleme en une fois. Pour connaitre l heure de son arrivée,
ca c apparente à de la genetique. Dans cette formule biologique, la résolution du problème
ou de la maladie n est donc pas de la chance mais c est trouvable par un calcul intelligent.