Circuits arithmétiques avec ,

Considérons un circuit qui prend comme nombres d'entrées dans $[0,1]$ et a des portes qui se composent des fonctions $\max(x, y)$ , $\min(x, y)$ , $1 - x$ et $\frac{x+y}{2}$ . La sortie du circuit est alors également un nombre en $[0,1]$ .

Quelqu'un sait-il si ce modèle, ou un modèle étroitement apparenté, a été étudié?

Plus précisément, j'essaie de résoudre le problème de satisfiabilité pour ce circuit, à savoir le calcul de la valeur maximale qui peut être atteinte par ce circuit (il atteint en effet un maximum, car il représente une fonction continue dans un domaine compact).

Remarque: mon étude de ce modèle se fait via des logiques temporelles pondérées, donc tous les modèles qui s'y rapportent pourraient également être utiles.

arithmetic-circuits Shaull
la source

Ce problème est sûrement NP-difficile. (Par satisfiabilité: vous avez

x \lor y \equiv max {x, y}

$x\vee y \equiv \max\{x,y\}$ et

\neg x \equiv 1 - x

$\neg x \equiv 1 - x$ , avec lesquels vous pouvez faire AND, OR et NOT.) Donc, votre question est-elle de savoir si ou non ce problème est en NP? La question de la décision de savoir si un tel circuit a une entrée qui donne la valeur 1 semble être en NP, car, s'il y a une telle entrée, il y en a une qui est 0/1.

Neal Young

Si nous choisissons de façon non déterministe l'une des valeurs de vérité possibles pour , où sont toutes des paires de nœuds de telle sorte qu'un nœud ou apparaisse dans le circuit, cela se transforme en un problème de programmation linéaire, qui est résoluble en P. Ainsi, la version de décision du problème de maximisation d'origine est en NP. (Il s'agit d'une variante du problème de satisfiabilité dans la logique de Łukasiewicz, vous pouvez donc consulter le chapitre de Haniková dans le Handbook of Mathematical Fuzzy Logic pour des informations connexes.)

\leq 2^{n}

$\le2^n$

x \leq y

$x\le y$

x, y

$x,y$

min (x, y)

$\min(x,y)$

max (x, y)

$\max(x,y)$

Emil Jeřábek

@Shaull: Permettez-moi de le décrire plus en détail. Soit les nœuds du circuit qui sont des portes min ou max (ici est limité par la taille du circuit), et soit et les nœuds d'entrée de la porte . Pour chaque , choisissez une contrainte supplémentaire ou . Il y a tels choix. Lorsqu'un tel choix est fixé, vous pouvez simplifier le circuit en remplaçant par ou

{a_{i} : i < m}

$\{a_i:i<m\}$

m

$m$

b_{i}

$b_i$

c_{i}

$c_i$

a_{i}

$a_i$

i < m

$i<m$

b_{i} \leq c_{i}

$b_i\le c_i$

c_{i} \leq b_{i}

$c_i\le b_i$

2^{m}

$2^m$

a_{i}

$a_i$

b_{i}

$b_i$

c_{i}

$c_i$ le cas échéant, il se transforme donc en un système d'équations linéaires dont les variables sont les variables d'origine du problème, et des variables supplémentaires correspondant à ...

Emil Jeřábek

... nœuds dans le circuit. Inclure inégalités indiquant que les contraintes supplémentaires sont satisfaites, inégalités limitant les variables d'origine à , et une inégalité indiquant que le nœud de sortie a la valeur . Il s'agit alors d'un programme linéaire dépendant du choix des contraintes supplémentaires, et le circuit atteint la valeur ssi il existe un choix des contraintes tel que le programme linéaire associé ait une solution.

m

$m$

[0, 1]

$[0,1]$

\geq u

$\ge u$

\geq u

$\ge u$

Emil Jeřábek

Notez également que la valeur optimale d'un programme linéaire est atteinte à un sommet du polytope. Cela signifie que le dénominateur de la solution optimale peut être exprimé comme un déterminant d'une matrice de dimension dont les entrées sont des entiers de taille constante, et il n'y a que entrées non nulles dans chaque ligne, et en tant que tel, il est délimité par .

O (n)

$O(n)$

O (1)

$O(1)$

2^{O (n)}

$2^{O(n)}$

Emil Jeřábek

Réponses:

Le problème de satisfiabilité pour ces circuits (c'est-à-dire, étant donné un circuit et , décider s'il y a une entrée telle que ) est dans NP, et donc NP-complet par Commentaire de Neal Young et réponse de Peter Shor. $C$ $u\in[0,1]$ $x$ $C(x)\ge u$

Nous pouvons construire une réduction non déterministe du problème à la programmation linéaire de la manière suivante. Soit tous les nœuds de qui sont des portes min ou max (ici , où est la taille du circuit), et soit et les nœuds d'entrée de la porte . Pour chaque , choisissez l'une des deux contraintes supplémentaires ou (il y a choix possibles au total). Lorsqu'un tel choix est fixé, on peut simplifier le circuit en remplaçant chaque par ou $\{a_i:i<m\}$ $C$ $m\le n$ $n$ $b_i$ $c_i$ $a_i$ $i<m$ $b_i\le c_i$ $c_i\le b_i$ $2^m$ $a_i$ $b_i$ $c_i$ le cas échéant, et le circuit résultant peut être décrit par un système de équations linéaires dont les variables sont les variables d'entrée d'origine du circuit, et des variables supplémentaires correspondant aux noeuds du circuit. $n$

Nous incluons également inégalités indiquant que les contraintes supplémentaires sont satisfaites, les inégalités limitant les variables d'entrée d'origine à , et une inégalité indiquant que le nœud de sortie a la valeur . Il s'agit alors d'un programme linéaire de taille selon le choix des contraintes supplémentaires, et le circuit atteint la valeur ssi il existe un choix des contraintes tel que le programme linéaire associé ait une solution. La programmation linéaire étant en P, cela montre que le problème est en NP. $m$ $[0,1]$ $\ge u$ $O(n)$ $\ge u$

Notez également que la valeur optimale d'un programme linéaire est atteinte à un sommet du polytope. Cela signifie que le dénominateur de la solution optimale peut être exprimé comme déterminant d'une matrice carrée de dimension dont les entrées sont des entiers de taille constante, et qu'il n'y a que entrées non nulles dans chaque ligne, et en tant que telles il est délimité par . $O(n)$ $O(1)$ $2^{O(n)}$

Des réductions de ce type sont souvent utiles pour donner des limites supérieures sur la complexité de la satisfiabilité dans les logiques floues propositionnelles (telles que la logique de Łukasiewicz) et les systèmes associés. (En fait, le problème d'origine est une variante mineure de la satisfiabilité dans Łukasiewicz, qui correspondrait à des circuits avec au lieu de ) Un aperçu des résultats connexes peut être trouvé dans le chapitre X du Manuel de logique floue mathématique, vol. II. $\min(1,x+y)$ $(x+y)/2$

Emil Jeřábek
la source

Ce problème est NP-difficile.

Vous pouvez obtenir 3-SAT avec les portes min ( x , y ), max ( x, y ) et 1− x .

Ce que nous voulons, c'est réduire un problème 3-SAT à un circuit pour lequel vous pouvez obtenir 1 si toutes les variables sont satisfaisables, et vous ne pouvez obtenir quelque chose de strictement inférieur à 1 sinon.

Nous pouvons forcer toutes les variables à être 0 ou 1 en prenant un minimum de beaucoup d'expressions, et faire en sorte que ces expressions incluent max ( x , 1− x ).

Maintenant, pour chaque clause du problème 3-SAT x ∨ y ∨ z , nous mettons l'expression max ( x , y , z ) au minimum.

Je ne sais pas quelle est la valeur optimale pour un problème 3-SAT non satisfaisable, mais ce sera strictement inférieur à 1.

Peter Shor
la source

Oui, la dureté NP est la "direction facile", comme indiqué dans un commentaire ci-dessus. En fait, si vous n'utilisez pas la porte moyenne, mais seulement min et max, il est facile de montrer que la valeur maximale est 1 si le circuit booléen correspondant est satisfaisable, et 1/2 sinon (simplement en branchant 1/2 à tous les variables). Quoi qu'il en soit, le problème a été résolu dans les commentaires ci-dessus.

Shaull

Pas exactement ce que vous avez demandé, mais un contexte dans lequel des circuits similaires apparaissent.

Si vous supprimez la porte (ce qui n'est même pas mentionné dans le titre!), Vous obtenez alors un circuit arithmétique monotone. Les limites inférieures du circuit monotone classique de Razborov ont été étendues aux circuits arithmétiques monotones (avec les mêmes résultats) par Pavel Pudlák, Bornes inférieures pour la résolution et les preuves des plans de coupe . $1-x$

Yuval Filmus
la source

Merci. Dans ce cas, cependant, si vous supprimez la porte , le problème est trivial - la valeur maximale est 1 et elle est atteinte lorsque toutes les variables obtiennent la valeur 1.

1 - x

$1-x$

Shaull