Article contents
Structure with fast elimination of quantifiers
Published online by Cambridge University Press: 12 March 2014
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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2006
References
REFERENCES
- 2
- Cited by