Structure with fast elimination of quantifiers
Prunescu, Mihai
J. Symbolic Logic, Tome 71 (2006) no. 1, p. 321-328 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
A structure of finite signature is constructed so that: for all existential formulas ∃y⃗ φ(x⃗,y⃗) and for all tuples of elements ⃗ of the same length as the tuple x⃗, one can decide in a quadratic time depending only on the length of the formula, if ∃y⃗ φ(u⃗,y⃗) holds in the structure. In other words, the structure satisfies the relativized model-theoretic version of P=NP in the sense of [4]. This is a model-theoretical approach to results of Hemmerling and Gaßner.
Publié le : 2006-03-14
Classification:  03B05,  03B25 
@article{1140641177,
     author = {Prunescu, Mihai},
     title = {Structure with fast elimination of quantifiers},
     journal = {J. Symbolic Logic},
     volume = {71},
     number = {1},
     year = {2006},
     pages = { 321-328},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1140641177}
}

Prunescu, Mihai. Structure with fast elimination of quantifiers. J. Symbolic Logic, Tome 71 (2006) no. 1, pp.  321-328. http://gdmltest.u-ga.fr/item/1140641177/