Structure with Fast Elimination of Quantifiers

Journal of Symbolic Logic 71 (1):321 - 328 (2006)
  Copy   BIBTEX

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,466

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Quantifier Elimination for Neocompact Sets.H. Jerome Keisler - 1998 - Journal of Symbolic Logic 63 (4):1442-1472.
Rings Which Admit Elimination of Quantifiers.Bruce I. Rose - 1978 - Journal of Symbolic Logic 43 (1):92-112.
Magidor-Malitz Quantifiers in Modules.Andreas Baudisch - 1984 - Journal of Symbolic Logic 49 (1):1-8.
Semi-Bounded Relations in Ordered Modules.Oleg Belegradek - 2004 - Journal of Symbolic Logic 69 (2):499 - 517.
Rings Which Admit Elimination of Quantifiers.Chantal Berline - 1981 - Journal of Symbolic Logic 46 (1):56-58.
The Evolution of Rational Demons.Colin Allen - 2000 - Behavioral and Brain Sciences 23 (5):742-742.

Analytics

Added to PP
2010-08-24

Downloads
20 (#559,094)

6 months
1 (#417,143)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Outline of a Theory of Truth.Saul Kripke - 1975 - Journal of Philosophy 72 (19):690-716.
Non-Effective Quantifier Elimination.Mihai Prunescu - 2001 - Mathematical Logic Quarterly 47 (4):557-562.

Add more references