Structure with fast elimination of quantifiers
Mihai Prunescu · Journal of Symbolic Logic · 2006
Abstract A structure of finite signature is constructed so that: for all existential formulas and for all tuples of elements of the same length as the tuple one can decide in a quadratic time depending only on the length of the formula, if holds in the structure. In other words, the structure satisfies the relativized model-theoretic version of P=N P in the sense of [4]. This is a model-theoretical approach to results of Hemmerling and Gaßner.