Complexity, Decidability and Completeness

Journal of Symbolic Logic 71 (2):399 - 424 (2006)
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 9,360
External links
  •   Try with proxy.
  •   Try with proxy.
  • Through your library Configure
    References found in this work BETA

    No references found.

    Citations of this work BETA

    No citations found.

    Similar books and articles
    Lauri Hella (1996). Logical Hierarchies in PTIME. Information and Computation 129 (1):1--19.
    Barbara F. Csima (2004). Degree Spectra of Prime Models. Journal of Symbolic Logic 69 (2):430 - 442.
    Harry Deutsch (1979). The Completeness of S. Studia Logica 38 (2):137 - 147.
    Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.

    Monthly downloads

    Added to index


    Total downloads

    8 ( #138,593 of 1,088,810 )

    Recent downloads (6 months)

    2 ( #42,743 of 1,088,810 )

    How can I increase my downloads?

    My notes
    Sign in to use this feature

    Start a new thread
    There  are no threads in this forum
    Nothing in this forum yet.