Recherche d'une structure algébrique
Quelqu'un aurait-il un exemple d'algèbre ayant les propriétés suivantes :
1. Des générateurs $a_1,a_2,\dots,a_K,b_1,b_2,\dots b_K,c_1,c_2,\dots c_K,\dots$
(avec $K$ fini ou non et le nombre de lettres fini ou non aussi).
2. Les relations : $x_i.x_i=x_i$ et $x_i.y_i=0$ pour $x\not=y$.
Merci (et meilleurs vœux).
1. Des générateurs $a_1,a_2,\dots,a_K,b_1,b_2,\dots b_K,c_1,c_2,\dots c_K,\dots$
(avec $K$ fini ou non et le nombre de lettres fini ou non aussi).
2. Les relations : $x_i.x_i=x_i$ et $x_i.y_i=0$ pour $x\not=y$.
Merci (et meilleurs vœux).
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans ton cas très précis, il suffit de quotienter l'algèbre (sur le corps que tu veux, ou sur les entiers) des polynômes en toutes les variables que tu veux par l'idéal engendré par $x_i^2-x_i$ et $x_iy_j$.
Matth Coss : merci...ce n'est pas exactement un exemple comme je voudrais mais plutôt une refonte dans une structure particulière.
Merci Christophe.
D'autres exemples ????
Pour $D \subset M_n(k)$ l'algèbre commutative des matrices diagonales $n\times n$ sur un corps, on a $D = vect(E_{1,1},E_{2,2},\dots,E_{n,n})$, avec $E_{i,i}$ remplie de 0 sauf pour un $1$ à l'intersection de la $i$ème ligne et de la $i$ème colonne.
Alors voici l'explication du pourquoi et du comment.
On part encore d'une formule $F$ du calcul propositionnel composée de clauses $C_1\wedge...C_K$ sur des variables $a,b,c,...$
On va faire de la combinatoire et calculer la proportion $R$ des produits possibles de littéraux qui ne contiennent pas au moins une paire de littéraux opposés comme $x,\lnot x$.
En réfléchissant un peu, ce ratio $R$ est égal au produit des $(1-x_i.x_j)$ pour chaque paire de clauses $C_i,C_j$ qui contient une paire $x,\lnot x$.
Ceci modulo certaines relations et avec des valeurs appropriées.
Ainsi pour $F=(a\vee b\vee x)\wedge (\lnot a\vee\lnot b)(a\vee c\vee\lnot d)$ on obtient :
$$R=(1-a_1a_2)(1-b_1b_2)(1-a_2a_3)$$
Si on applique les relations $x_i.x_i=x_i$ et $x_i.y_i=0$ pour $x\not=y$ et que l'on remplace chaque $x_i$ par l'inverse de la taille de $C_i$, on obtient exactement la valeur de ce ratio.
Dans l'exemple on obtient $R=1-a_1a_2-a_2a_3-b_1b_2+a_1a_2a_3$ et avec les valeurs $a_1=b_1=1/3,a_2=b_2=1/2,a_3=b_3=1/3$
on trouve bien la valeur $R=5/9$ qui est exactement la proportion de "bons" produits.
En effet il y a $10$ produits sans paire de littéraux opposés, soit $(5/9).3.2.3$.
Remarquez que si on se restreint aux instances de 3SAT, tous les $x_i$ seront évalués à $1/3$.
Pour le problème SAT, ce que l'on souhaite c'est pouvoir décider si $R=0$ ou non.
Ce qui serait bien sûr souhaité c'est une structure de corps commutatif avec les propriétés énoncées.
Le fait de faire des tirages au sort AVANTAGE énormément, contre des stratégies déterministes. Par exemple, trivialement, en tirant au sort une suite de $10^{10^{10} }$ éléments de $\{0;1\}$, on gagne sans aucun effort au défi de produire une $s$ telle que le plus petit algo produisant $s$ fait au moins 10000 mots informatiques.
Or aucun algorithme n'est capable d'en faire autant. Il résulte qu'en "embarquant" ce fait dans divers circuits camouflant, on peut produire des "tours de magies" qui peuvent faire grand effet sur un public de sectateurs scientifiques.
L'exemple historique est la preuve de $(**):=PSPACE \subset IP$ que tu peux d'ailleurs facilement simplifier en preuve de $coNP \subset IP$ en créant déjà un effet émotionnel très puissant sur ton public.
Peut-être pourrais-tu (si tu ne le connais pas déjà) regarder la preuve de (**), car il me semble qu'elle t'intéresserait au plus haut point.
Si je parle d'entourloupe, c'est bien sûr sympathique, c'est juste pour rappeler que de tels résultats ne nous sont utiles qu'en présence du constat que la Nature suit les lois quantiques, donc, entre autre, rend "réel" les générateurs aléatoires.
En termes algorithmiques purs, ça n'a aucun valeur sans vrai hasard, puisque les générateurs dits pseudo-aléatoires sont évidemment polynomiaux (et même linéaires le plus souvent), et donc si on leur appliquait le théorème (**), avec le dogme qu'on peut leur faire confiance, donneraient pas seulement $P=NP$, mais carrément, excuse du peu:
[size=x-large]$$ P = PSPACE $$[/size]
Autrement dit, on peut te faire la remarque suivante: ton profil de recherche actuel ne semble pas chercher à prouver seulement que $P = NP$, mais bel et bien que $P = PSPACE$ ce qui parait encore nettement plus ambitieux.
oui, je suis conscient de cela. Je relativise autant la notion d'aléatoire que la notion d'espace.
Ainsi, avec cette approche de ratio (et des variantes dont je n'ai pas (encore) parlé ici), on peut obtenir un nombre rationnel qui "code" le résultat et pouvant être assez énorme.
Ceci dit, quand on en revient à la base d'une machine de Turing, en une étape on explore au plus une case de plus.
Alors en temps $T$, on utilise au plus un espace $P\le T$....mais ce n'est peut être plus le cas en calcul quantique.
Un autre indice sympathique pour relier le déterminisme au non déterminisme se trouve dans le théorème de Savitch qui implique : $$P(SPACE) = NP(SPACE)$$
Du coup ça me semble un peu étonnant de le voir comme un indice non?
De mon téléphone