Abstract

A structure of finite signature is constructed so that: for all existential formulas $\exists ??\varphi (??,??)$ 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 $\exists ??\varphi (??,??)$ 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