Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2025-01-03T11:09:41.603Z Has data issue: false hasContentIssue false
  • English
  • Français

Structure with fast elimination of quantifiers

Published online by Cambridge University Press:  12 March 2014

Mihai Prunescu
Mihai Prunescu*
Affiliation:
Abteiling für Mathematische Logik, Universität Freiburg, Ecker STR. 1, D-79103 Freiburg im Breisgau, Germany I. M. A. R. (Institutul de Matematica“Simion Stoilow” al Academiei Romane) Calea Grivitei STR. 21, Ro-010702 Bucharest, Romania. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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
The Journal of Symbolic Logic , Volume 71 , Issue 1 , March 2006 , pp. 321 - 328
Copyright
Copyright © Association for Symbolic Logic 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Gaßner, Christine, A structure of finite signature with identity relation and with P = NP—A formal proof, preprint, Universität Greifswald, 2004.Google Scholar
[2]Hemmerling, Armin, P = NP for some structures over the binary words, Journal of Complexity, vol. 21 (2005), no. 4, pp. 557–578.CrossRefGoogle Scholar
[3]Kripke, Saul, Outline of a theory of truth, The Journal of Philosophy, vol. 72 (1975), no. 19, pp. 690–716.CrossRefGoogle Scholar
[4]Poizat, Bruno, Les petits cailloux, ALEAS, Lyon, 1995.Google Scholar
[5] Poizat, Bruno, Une tentative malheureuse de construire une structure eliminant rapidement les quanteurs, Lecture Notes in Computer Science, vol. 1862, 2000, pp. 61–70.Google Scholar
[6]Prunescu, Mihai, Non-effective quantifier elimination, Mathematical Logic Quarterly, vol. 47 (2001), no. 4, pp. 557–561.3.0.CO;2-O>CrossRefGoogle Scholar