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 tree represents the set of complete consistent extensions of
some theory which is 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.