Complexity, Decidability and Completeness

Journal of Symbolic Logic 71 (2):399 - 424 (2006)
  Copy   BIBTEX

Abstract

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 97,078

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

Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Polynomial games and determinacy.Tomoyuki Yamakami - 1996 - Annals of Pure and Applied Logic 80 (1):1-16.
Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.
Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.

Analytics

Added to PP
2010-08-24

Downloads
106 (#172,204)

6 months
24 (#161,129)

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

Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Polynomial-time versus recursive models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
Complexity-theoretic algebra II: Boolean algebras.A. Nerode & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 44 (1-2):71-99.

View all 8 references / Add more references