Les circuits AND & OR sont-ils P-complets?

La porte ET & OU est une porte qui reçoit deux entrées et renvoie leur ET et leur OU. Les circuits fabriqués uniquement à partir de la porte AND & OR, sans fanout, sont-ils capables de faire des calculs arbitraires? Plus précisément, l'espace de journalisation du calcul du temps polynomial est-il réductible aux circuits ET & OU?

Ma motivation pour ce problème est plutôt étrange. Comme décrit ici , cette question est importante pour le calcul dans le jeu informatique Dwarf Fortress .

Si je ne comprends pas mal ce que vous entendez par porte ET & OU, il s'agit essentiellement d'une porte comparateur qui prend deux bits d'entrée et et produit deux bits de sortie et . Les deux bits de sortie et sont essentiellement min et max .y x ∧ y x ∨ y x ∧ y x ∨ y ( x , y ) ( x , y $x$$y$$x\wedge y$$x\vee y$$x\wedge y$$x\vee y$$(x,y)$$(x,y)$

Les circuits de comparaison sont construits en composant ces portes de comparaison ensemble mais en ne permettant plus de fan-out autres que les deux sorties produites par chaque porte . Ainsi, nous pouvons dessiner des circuits de comparaison en utilisant les notations ci-dessous (de la même manière que nous dessinons des réseaux de tri).

Nous pouvons définir le problème de la valeur du circuit du comparateur (CCV) comme suit: étant donné un circuit comparateur avec des entrées booléennes spécifiées, déterminer la valeur de sortie d'un fil désigné. En prenant la fermeture de ce problème CCV sous des réductions d'espace de log, nous obtenons la classe de complexité CC , dont les problèmes complets incluent des problèmes naturels comme l'appariement maximal lex-premier, le mariage stable, le colocataire stable.

Dans ce récent article , Steve Cook, Yuval Filmus et moi-même avons montré que même lorsque nous utilisons une fermeture à plusieurs AC , nous obtenons toujours la même classe CC. Au meilleur de nos connaissances à ce stade, NL CC P. Dans notre article, nous avons fourni des preuves que CC et NC sont incomparables (de sorte que CC est un sous-ensemble approprié de P), en donnant des paramètres Oracle où CC relativisé et NC relativisés sont incomparables. Nous avons également témoigné que CC et SC sont incomparables. ⊆ $^0$$\subseteq$$\subseteq$

(la réponse n'est pas éligible car elle fait référence à des portes ET, OU séparées sans restriction de fan out)

L'article suivant porte sur le sujet: Automates cellulaires à vote majoritaire, dynamique des ises et exhaustivité P

Nous montrons qu'en trois dimensions ou plus ces systèmes peuvent simuler des circuits booléens de portes ET et OU, et sont donc P-complets . C'est-à-dire que la prévision de leur état t des pas de temps dans le futur est au moins aussi difficile que tout autre problème qui prend du temps polynomial sur un ordinateur série.

(...)

Le problème de valeur de circuit monotone, où les portes ET et OU sont autorisées mais pas les portes, n'est toujours pas P-complet pour la raison suivante: en utilisant les lois de De Morgan (...), nous pouvons reculer les négations à travers les portes jusqu'à ce qu'elles ne affecter les entrées elles-mêmes. Ainsi, tout problème de valeur de circuit peut être converti en un problème de valeur de circuit monotone avec certaines des entrées annulées. Ce type de conversion, d'une instance d'un problème à une instance d'un autre, est appelé une réduction.