Projet $P\not=NP$

serge burckel

J'aurais du mal à faire plus simple.

Un des objectifs de cette présentation simple est d'inviter les spécialistes de complexité descriptive à la reformuler et la vérifier.

Rappel : En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles qui caractérise les classes de complexité en termes de logique.

serge burckel

Je pense que c'est l'essence d'une preuve de $P\not=NP$.
Le reste n'est que complications techniques et adaptations à des définitions originelles pas forcément bien adaptées.

serge burckel

Pour marquer le coup et pour le "fun", j'ai soumis aujourd'hui cette page en français sur arXiv.
Là il n'y a pas de référence à sigle.space...c'est donc moins "space" et cela devrait donc passer comme une lettre à la poste….lol ;-)

serge burckel

une petite conclusion...il y avait tout juste la place sur la page...ouf ! ;-)

serge burckel

arXiv rejette encore une fois...c'est compliqué de diffuser des trucs simples.
Vais donc l'envoyer à une revue genre Spirou.

This repository is only for substantive self-contained scientific research results that would be considered refereeable for publication in a conventional journal. Our moderators have determined that your submission is not of plausible interest for arXiv.

As a result, we have removed your submission.

For feedback, consider sending this to a conventional journal.

serge burckel

Bonjour

J'ai repensé l'exposé pour clarifier certains points abordés dans la conclusion. C'est ainsi plus complet (enfin je pense).

serge burckel

Allègement de la définition d'effectivité en ne considérant que des opérations en "ROM".

serge burckel

Quelques reformulations avant d'envoyer à...….arXiv !

C'est devenu une obsession d'enfin réussir à être "publié" sur arXiv qui ne se prend vraiment plus pour de la daube. Genre : ce que vous faites n'est pas digne de nous mais vous pouvez publier cette merde dans une revue classique comme Science ou le Lancet (oups...pardon, ce n'est plus un bon exemple ;-) )

serge burckel

Bonjour,

voici une reformulation avec 2 rubans : une ROM et une RAM...c'est quand même plus clair ainsi.

serge burckel

Encore quelques précisions et éclaircissements.

serge burckel

Un point de calcul. Pour faire de la simulation vraiment neutre et que cela le reste par récurrence si on simule une machine qui elle-même simule un calcul etc....il faut commencer par recopier le mot d'entrée donné en ROM sur le ruban de travail. La complexité est donc au minimum linéaire.

Tout ça c'est uniquement pour que la simulation d'un calcul qui atteindrait la borne de $n^K$ étapes avec $K=10^{10000000}$ ne dépasse pas cette borne en multipliant par $n$....
big big big LOL....mais bon.

serge burckel

Bon, c'était saoulant ces considérations de techniques de ROM, RAM etc....alors j'ai formalisé l'essentiel….
ouf, c'est beaucoup plus clair ainsi.

CLIC

serge burckel

P différent de NP....Simple comme un clic ?

serge burckel

Version en anglais...traduction vite fait pour soumettre à une revue. Mais je voulais plutôt le publier en français.

Quelqu'un sait si la revue "Technique et Science Informatique" existe toujours ?

merci

serge burckel

Je me sens un peu seul sur ce fil. Comme quelqu'un qui ferait un exposé devant un auditoire muet. Alors je reformule encore et encore jusqu'à obtenir enfin une réaction. Alors je me relève dans la nuit pour rédiger une nouvelle formulation.

Voici.

serge burckel

Là j'explique le truc.

serge burckel

Je continue à parler tout seul. Voici donc la suite.

Mais j'en profite pour ouvrir un débat de fond et de forme.

J'aimerais bien que les preuves en maths soient exposées ainsi :

a) on part du résultat en notant les points délicats.
b) on explique ces points et on arrive aux hypothèses qui solutionnent ces points.

Bref, faire l'exposé du résultat de manière à ce qu'un lecteur puisse penser à d'autres manières de le trouver.
C'est également la manière de trouver une preuve de la plupart des gens. On pense à l'objectif et on trouve les moyens de l'atteindre.

serge burckel

Je peux encore simplifier et clarifier en oubliant tous ces clics (qui me saoulent aussi à la longue).

Tout ce que l'on demande, c'est la possibilité de faire des appels à des procédures comme le font tous les programmes.

Je le rédige….voilà

serge burckel

encore quelques précisions avant de soumettre à une revue.

des suggestions ? des corrections ?

merci à vous

serge burckel

Voilà la version soumise à un journal ce soir

raoul.S

Good luck.

serge burckel

Merci c'est gentil...enfin une réaction !

Bon, ce n'est pas une question de chance...enfin je crois…je suppose...j'espère
C'est non déterministe aussi l'acceptation d'un papier ?
Oui, peut-être, en effet.

raoul.S

Ben vu ton expérience précédente avec arXiv j'espère pour toi que c'est non déterministe.

Personnellement je n'y connais presque rien en calculabilité (enfin si c'est bien de la calculabilité dont il s'agit), donc à part de souhaiter bonne chance... (tu)

Alesha

Tu prétends prouver P^E /= NP^E pour ta variante sur la manière de compter le nombre d'étapes et, en conclusion, tu dis penser que cette preuve pourrait être un modèle pour montrer P /= NP avec les définitions usuelles. Ce que je ne comprends pas, c'est que:
- ou bien tu ne vois pas comment prouver P /= NP avec ta variante, et alors, je ne vois pas pourquoi tu dis que ta preuve peut servir de modèle avec les définitions habituelles;
- ou bien tu vois comment passer de P^E /= NP^E à P /= NP (avec ta variante) et je ne comprends pas pourquoi tu prives le lecteur de ce résultat crucial.
A priori, on pourrait avoir un problème dans NP^E qui ne soit pas dans P^E mais qui soit dans P^{E'} pour un certain E' /= E. Soit tu as un argument pour expliquer que ça ne peut pas être le cas, et tu devrais le donner; soit tu ne l'as pas, et on n'a pas de modèle pour une preuve de P /= NP avec les définitions usuelles.

serge burckel

Bonnes remarques @Alesha

C'est à peu près ça. Je ne sais pas faire des preuves en passant aux limites.
Comme je l'ai déjà dit sur ce forum, je ne crois pas aux infinis, même pas à celui les entiers.
Par contre la variante définie par le nombre ordinal $\omega$ plus grand que tous les entiers et surtout d'un autre type, j'y crois.

Alors passer d'un argument finitiste (même aussi grand que concevable et au delà du réalisable) à l'infini,
je ne sais pas faire et surtout, je ne veux pas le faire. Je laisse cela à d'autres et je ne sais pas si c'est simple ou non.

(ci jointe, version un peu révisée...mais toujours finitiste)

serge burckel

Pour poursuivre le débat,

je trouve que la définition standard $P=\cup_k DTIME(n^k)$ n'a aucun sens pratique et aucune utilité pour faire mieux que de l'exponentielle.

Pour tout $n$, il y aura toujours un $k$ tel que $n^k>2^n$...genre à partir de $nlog(2)/log(n)$

serge burckel

Alors en effet, si le déterminisme est moins puissant que le non déterminisme au niveau $E$, il peut exister un niveau supérieur $E'$ où
$DET(E')$ rattrape $NONDET(E)$. Mais alors $NONDET(E')$ est encore plus puissant que $DET(E')$ etc...
On en conclut quoi ? Pour ma part, je n'en sais rien du tout. C'est trop abstrait ou casse gueule pour m'aventurer dans ce territoire.

Il faut se fixer des limites sur quelque chose….enfin c'est mon avis.

La complexité en temps ou en espace ou encore la taille des machines.
Parce que, même là, on peut grossir les machines (à l'infini) pour que tout devienne linéaire comme un automate fini.
On peut au fur et à mesure grossir les machines pour intégrer les réponses pour des mots d'entrée de plus en plus longs.
Vous comprenez, avec des réponses précalculées. Et on tombe dans le même genre d'argumentaire répétitif qui part aussi vers l'infini.

Je veux montrer par là qu'un argumentaire semblable à celui d'Alesha peut aussi conduire à montrer que $P=LIN$ où $LIN$ est l'ensemble des problèmes décidés en temps linéaire (pensez à un automate fini qui lit le mot une fois).

Tout devient égal vers l'infini si un paramètre peut en compenser un autre.

serge burckel

Je veux dire par là que, de manière générale en logique : certes, il y a l'ordre des quantificateurs qui donne l'ordre de priorité et de dépendance comme dans ce contexte :

il existe une machine M
il existe une fonction polynômiale p de N dans N
pour tout n
pour tout mot w de longueur n
tout calcul de M sur w se fait en p(n) étapes

mais si on veut comparer 2 formules du même type :

classe P
il existe une machine déterministe M
il existe une fonction polynomiale p de N dans N
pour tout n
pour tout mot w de longueur n
tout calcul de M sur w se fait en p(n) étapes

classe NP
il existe une machine non déterministe M'
il existe une fonction polynomiale p' de N dans N
pour tout n'
pour tout mot w' de longueur n'
tout calcul de M' sur w' se fait en p'(n') étapes

ça se complique si rien n'est borné
Les paramètres d'une formule peuvent s'adapter aux paramètres de l'autre formule et pas forcément à leur paramètre miroir.
Le p' peut s'adapter au p mais aussi au n etc...

Bref, fixer une limite sur un type de paramètre me semble être un minimum syndical pour parler de la même chose dans les deux formules.

Mais je veux bien apprendre à voir les choses autrement et à aller vers l'infini si quelqu'un m'accompagne en me prenant la main.

christophe c

Serge a écrit:

Merci c'est gentil...enfin une réaction !

Bin, tu mènes tes recherches en live sur le forum, c'est une idée que je ne juge pas du tout mal, mais "lire de la recherche" demande un investissement. Je me suis toujours dit qu'un jour je te lirai, mais je reporte, mais avec l'été, peut-être...

serge burckel

Je suis en train d'essayer de tenter de faire un essai pour intégrer les paramètres dans le formalisme.

Ce sera donc une révision : Relative & Effective Complexity.

En cours de rédaction….

umrk

"Ne pas croire aux infinis", c'est une idée originale, qui mérite d'être développée, car elle peut entraîner loin ..

serge burckel

Voilà l'idée de relativité. Il faut encore développer et préciser. Mais comme je le disais, le même schéma de preuve s'applique encore ici.

Je commence à établir les liens entre les complexités classiques et relativistes.

s

serge burckel

Bonjour,

Voici une petite refonte (en attendant les rapports des référés). Je continue en parallèle à intégrer une notion relative du temps de calcul pas forcément dépendante de la longueur des mots (ça semble tellement arbitraire cette convention historique)

serge burckel

Bonsoir,

voici une nouvelle note (1 page) qui intègre le temps de manière assez simple.
Cela permet d'affiner l'approche par Complexité Effective que je vous ai présentée.

serge

(cette note est soumise à une revue)

serge burckel

Je discute depuis deux jours avec Rupert McCallum qui me pose plein de questions sur "Effective Complexity" (article soumis).

C'est assez déroutant de voir qu'il ne pige pas la notion très classique de codage d'une Machine de Turing ou la définition d'un langage reconnu par une machine. Comme quoi, ce n'est pas le même domaine. Mais cela montre aussi que mon papier requière des bases pour être lu.
En 2 pages, je ne vais pas faire un Survey. Des amis me demandent d'écrire des livres...lol.
OK pour un livre de 3 pages alors ;-)

serge burckel

Après, c'est réciproque. Je ne comprends rien du tout à ce qu'il fait dans sa preuve.
Je ne pige même pas le titre. Du coup, question incompétence à comprendre l'autre, je gagne haut la main. :-P

serge burckel

Les nombreuses questions de Rupert m'ont poussé à "mieux" expliquer certains points.
Ravi que cette note l'intéresse et qu'il prenne bien le temps de comprendre.

Voici la version "détaillée" (mais toujours en 2 pages)

serge burckel

Autre article soumis (dans un autre journal) et qui traite plus précisément de la complexité en temps polynomial.
Ceci en réponse aux questions de @Alesha.

serge burckel

Durant la préparation d'un troisième article, voici une avancée pour le second où $P^R\not=NP^R$ devient $P\not=NP^R$
Dans le prochain article, on sera encore plus proche de $P\not=NP$.

serge burckel

Voici la première version du troisième article.

serge burckel

Voici la version soumise ce soir à une autre revue.

serge burckel

Voici une dernière version (soumise à un autre journal...je sème) qui donne un cadre général et des conditions suffisantes sur les classes de complexité pour être séparées dans le déterminisme et le non déterminisme.

serge burckel

Preuve quasi complète de $P\not=NP$. Il reste à détailler la fin.

Maxtimax

Salut Serge,
Je n'ai pas tout suivi, mais puisque tu es en contact avec lui, sais-tu où en est le manuscrit de Rupert ? Y a-t-il eu des corrections, des erreurs, etc. ?

serge burckel

@Maxtimax

Rupert m'a dit qu'il a soumis chez "Annals of Mathematics"

Il y a des critiques comme il m'écrit :

<<"Annals of Mathematics" are taking a while to respond, but we'll see how we
go. Henry Towsner has given critical feedback on it, so yes you are not the
only one who finds that other experts end up asking for clarifications.>>

Sinon, je vous prépare une preuve de $P\not=NP$ ce soir....le puzzle est complet....ouf ! J'espère finir ce soir ou demain.
C'était assez difficile de faire rentrer mes astuces dans le formalisme classique...mais c'est bon, ça rentre...il faut juste considérer des mots très très très gros.

raoul.S

1'000'000 $ (:D

serge burckel

Voici donc la première ébauche de la preuve finale.

ai corrigé quelques coquilles,
modifié la définition de $L^*$


Alors c'est encore à relire avant d'envoyer à une revue....mais surtout pas à arXiv !!!! ::o

Bien entendu je suis ouvert à toute correction/remarque/question.

J'en profite d'ailleurs pour remercier encore une fois @alesha qui m'a motivé pour rentrer dans le cadre classique de P et NP.

christophe c

De mon téléphone : tu disposes de HAL si tu refuses aRxIv

serge burckel

@christophe, merci du conseil.

voilà, c'est déposé sur HAL et aussi envoyé à une bonne revue.

Maxtimax

"you are not the only one who finds that other experts end up asking for clarifications" : cette remarque m'étonne... S'il y a des critiques à faire, on ne peut s'étonner qu'elles soient faites, et pour quelque chose d'aussi important que $P\neq NP$ on ne peut pas s'attendre à ce que les relectures n'attaquent des points "de détail", ou ne demandent des clarifications...