On complexity reduction of Σ1 formulas

Archive for Mathematical Logic 42 (1):45-58 (2003)
  Copy   BIBTEX

Abstract

. For a fixed q  ℕ and a given Σ1 definition φ, where d is a parameter, we construct a model M of 1 Δ0 + ¬ exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ having no more than q alternations of blocks of quantifiers.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,346

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

The Role of Quantifier Alternations in Cut Elimination.Philipp Gerhardy - 2005 - Notre Dame Journal of Formal Logic 46 (2):165-171.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.
Deterministic chaos and computational complexity: The case of methodological complexity reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.

Analytics

Added to PP
2013-11-23

Downloads
9 (#937,492)

6 months
1 (#450,993)

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

No references found.

Add more references