An unsuccessful attempt to construct a structure quickly eliminating quantifiers

From MaRDI portal





De l'introduction: Je cherche à construire une structure \(M\) éliminant rapidement les quanteurs: à toute formule existentielle \((\exists{\mathbf y})\varphi({\mathbf x},{\mathbf y})\), ou \(\varphi\) est sans quanteurs, doit être associée une formule \(\psi({\mathbf x})\), également libre de quanteurs, qui lui soit équivalente dans \(M\), la longueur de \(\psi\) étant polynomialement bornée en fonction de celle de \(\varphi\); autrement dit, pour une certaine constante \(c\), \(|\psi|\leq |\varphi|^c\). Tant qu'à faire, j'aimerais aussi que \(\psi\) fût calculée par un algorithme polynomial à partir de \(\varphi\). Pourquoi je veux faire ça? Parce que si c'était vrai de la structure à deux éléments \(M= \{0,1\}\), dans le langage réduit à l'égalité et aux deux constantes 0 et 1 (ou même à la seule relation \(x=0!\)), eh bien on répondrait positivement à deux questions ouvertes en complexité, \(\text{NC}^1= \text{P}\) et \(\text{P}= \text{NP}\), version uniforme ou non suivant que l'élimination serait algorithmique ou pas (que ça implique \(\text{P} = \text{NC}^1\) vient de ce que j'écris les formules sous la forme usuelle, et non pas comme des circuits booléens). La même chose se produirait si la structure était finie, hormis le cas trivial d'une structure à un élément que nous excluons, ou bien si son langage fini ne comportait que des relations et pas de fonctions. For the entire collection see [Zbl 0944.00037].











This page was built for publication: An unsuccessful attempt to construct a structure quickly eliminating quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2753666)