Projet $P\not=NP$

christophe c

grr google ne la traduit pas car elle est mélangée avec le français. Tu peux me la traduire?

serge burckel

Ce n'est pas moi qui dit ça mais Rupert. Il répondait à mon message qui le remerciait pour toutes les questions qu'il me posait.
Et oui, en effet, je suis plutôt du genre à être demandeur de questions et de remarques sur des points importants ou des détails et même des fautes d'orthographe et je remercie les autres pour cela. C'est une aide. Surtout que je suis du genre à devoir être motivé pour travailler. Du coup, je me fixe tout seul des défis et des challenges et me mets la pression comme par exemple sur ce forum.

Pour traduire pour Christophe : "tu n'es pas le seul qui trouve que d’autres experts finissent par demander des éclaircissements »

Ah oui aussi, je lui disais que certaines de ses questions m'étonnaient (en sous-entendant qu'elles concernaient des notions très basiques) :

Rupert, well, let me answer to your questions (some of them are surprising me)

serge burckel

J'en profite dans une refonte de l'article pour présenter une idée qui m'est venue en rédigeant et qui généralise les mots "vecteurs".

Il s'agit d'extensions logiques d'ensembles. Pour cela on fabrique de nouveaux éléments de type [termes=formules du calcul propositionnel] comme par exemple $t=x\vee x\vee (y\wedge\lnot z)$ et pour un ensemble $S$ donné et un ensemble $T$ de tels termes, l'ensemble étendu $T/S$ est l'ensemble des termes $t$ de $T$ qui sont évalués à vrai en évaluant les atomes $x$ de $t$ par $x\in S$.
Pour l'exemple, cela donne
$$(x\in S)\vee (x\in S)\vee ((y\in S)\wedge (z\not\in S))$$

En particulier, puisque tout $x$ est un terme on aura pour tout ensemble $S$ et l'ensemble $\Gamma=\{x:vrai\}$ du "Tout" : $$\Gamma/S=S/S=S$$
$$\{x\vee x\}/S=\{x\vee x:x\in S\}$$
$$\{x\vee\lnot x\}/S=\{x\vee\lnot x\}$$

Pour deux ensembles $S$ et $T$ on aura $T/S=S/T=S\cap T$.

Cela ressemble à quelque chose de classique cette notion ?

En tout cas, c'est assez central dans ma construction pour $P/NP$.

je commence à le présenter là.

serge burckel

Voici la version reformulée avec des termes.

serge burckel

Bon, de mon côté, j'ai reçu des remarques comme quoi l'idée d'extensions logiques c'était bien mais ça complique ici.
Du coup, je vais simplifier et faire ce que je sais faire le mieux : du syntaxique.
Je rédige cela....
voilà

Martial

@Serge : je n'ai pas suivi tout ton parcours, pour cause d'incompétence notoire de ma part, mais si j'ai bien compris en quelques mois tu es passé de $P=NP$ à $P \neq NP$.

Peux-tu m'expliquer en quelques mots tes motivations ?

P.S. : aucune critique dans mes propos, c'est bien connu, il n'y a que les imbéciles qui ne changent pas d'avis...

serge burckel

@Martial

Comme déjà écrit quelque part sur ce forum, j'ai toujours travaillé sur les deux possibilités avec des idées pour les deux, l'une alimentant parfois l'autre. Sur ma proposition pour $P=NP$, j'attends toujours une preuve par Coq que c'est faux ou alors de développer un algorithme qui le prouve ou construise un contre-exemple....ce serait cool. Et sur cette question $P/NP$, je n'ai pas d'avis à priori. Mon seul sentiment déjà exprimé ici est que cette question n'est pas très importante et assez artificielle, tant sur le plan théorique que pratique. Déjà la définition de ces classes de complexité se passe à la limite...et vous savez ce que je pense des limites.
Exemple : pour des instances de taille $n>10^{10000000}$, le calcul se fait en $n^{100000000000000000000000}$...ok, c'est polynomial mais quel est l'intérêt ?

Je t'invite volontiers chez moi pour discuter de tout ça tranquillement.

serge burckel

Et donc, j'en suis venu à penser qu'il est plus important de changer de modèle de calcul et de façon de mesurer ces calculs.
C'est plutôt cela l'utilité de cette question P/NP et si elle permet de développer par exemple le calcul quantique, c'est bien.
Cela m'avait aussi conduit à considérer des calculs qui ne nécessitent pas de mémoire annexe.
Calculer une application $F$ de $S^n$ dans $S^n$ en transformant tout vecteur $V$ de $S^n$ en $F(V)$ par une séquence finie d'opérations sur les $n$ composantes de $V$ par des applications de $S^n$ dans $S$. J'avais montré que c'est toujours possible.

L'exemple classique (qui lui était connu) est celui de l'échange.
Pour échanger 2 registres $A$ et $B$, on fait en général en programmant : $C:=A, A:=B, B:=C$
Mais le $C$ est inutile et revient à utiliser un registre supplémentaire du processeur ou des appels en mémoire, bref...du temps ou de l'espace de perdu.
On peut faire : $A:=A+B, B:=A-B, A:=A-B$.
Sur des bits dans $\{0,1\}^2$, les $+$ et $-$ deviennent des XOR logiques.

Thm. Toutes les bijections ou les applications linéaires sur $\{0,1\}^n$ peuvent se réaliser comme ça en $2n-1$ étapes.
Les applications quelconques peuvent se réaliser en $4n-3$ étapes.

Sur les ensembles infinis comme $\N^n$, c'est plus simple : tout peut se faire en $n+1$ étapes.

serge burckel

Je prépare une nouvelle forme d'un article suite à des retours d'une revue.

Voici le début (traduit automatiquement en français pour vous....épées c'est pour swords)

Je ne sais pas si cela intéresse beaucoup de gens ici...je le fais au moins pour @alesha.

et voici la version plus complète en anglais.

serge burckel

Voici le nouvel article que je vais soumettre dans une autre revue....je multiplie ainsi les chances d'être lu et peut être compris.
Je trouve que c'est le plus complet et le plus concis....1 page et demi.

Et c'est difficile de passer les étapes....pour le moment, un seul des 4 articles est en mode reviewing.
Les autres sont encore avec les éditeurs qui ne doivent pas trop savoir quoi faire....."reject" / "accept" ;-)

serge burckel

Encore une version pour une autre revue....j'essaye que ça passe au moins entre les mains de rapporteurs.
Pour l'instant, c'est le cas pour 2 articles.

Pour Rupert Mc Callum, il m'a dit il y a quelques jours que ce n'est pas son cas : la revue Annals of Mathematics où il a soumis est "timide".

Martial

@Serge : Ruppert Mc Callum ? Tu tapes fort !

serge burckel

Je ne tape pas. Je l'avais contacté et nous communiquons un peu désormais. J'en avais déjà parlé ici.

christophe c

AOM ne publie que les trucs "déja publiés sur le fond". Il ne valide pas lui-même les choses. Dis à RMC de soumettre ailleurs.

serge burckel

Très bonne information @Christophe...je vais lui transmettre. Mais si tu veux, tu peux aussi lui écrire : *******@*******.****

son adresse est privée mais n'est pas confidentielle.

[Edit : puisque que cette adresse est supposée être privée, elle n'a pas à être rendue publique. Tu peux la communiquer par MP à CC. (T. P)]

serge burckel

Bon, je lui ai transmis ce soir l'information donnée par Christophe.

Sinon, pour préciser pour la modération de Thierry POMA, j'avais employé le terme "adresse privée" en opposition à "professionnelle" et non pas à "publique". Sinon, j'apprécie positivement qu'il y ait de la modération et un contrôle de ce qui se dit et partage sur les forums. Merci.

serge burckel

Voici un nouvel article pour une autre revue.
Contrairement à Rupert, je ne me focalise pas sur une seule revue.
Je n'essaye même pas de "soumettre" cela à ArXiv...ce serait encore refusé....LOL.

serge burckel

Un petit effort et voici une version traduite en français pour qui préfère.

serge burckel

Un point sur les soumissions :

Effective Complexity : en reviewing

Complexity classes for which determinism and non determinism are different : en reviewing

Closed Complexity Classes : en reviewing

Relatively Polynomial Complexity : avec éditeur

Intrinsic Complexity : soumis

serge burckel

Voici une révision en cours du dernier article.

serge burckel

Révision quasi terminée et complétée.

serge burckel

Révision envoyée...mais je rame toujours à rentrer dans le cadre classique...mon avis est qu'il faut sortir de ce cadre pour obtenir une preuve simple. Une preuve compliquée devrait consister à "déformer ce cadre...mais à tous petits coups de marteaux...sans que ça se voit".