4.3 Inclusions between Complexity Classes

When is a language L tractable?

L ∈ P, otherwise L is intractable.

When is a decision problem P tractable and what is the assumption made?

If the language Y(P) is in P (assuming polynomial-time encoding and decoding).

When is a language L decidable in exponential time

If there is a Turing machine M deciding L such that τM ∈ O(2^{n^r}) for some r ∈ N (natural numbers).

What is the class of all languages decidable in exponential time denoted by?

ExpTime

What is P ⊆ NP ⊆ PSpace equal to?

NPSpace ⊆ ExpTime

What is P not equal to?

ExpTime

Prove P ⊆ NP and PSpace ⊆ NPSpace:

→ Every TM can be converted into an equivalent NTM by turing hr into an ordinary state with δ(hr, a) = ∅ for each tape symbol a.

Prove NP ⊆ NPSpace:

→ Every NTM N satisfies s_N (n) ≤ τ_N (n) + 1, hence τ_N ∈ O(n^r )implies sN ∈ O(n^r).

Prove NP ⊆ NPSpace:

Prove PSpace ⊆ ExpTime:

What is Presburger arithmetic?

A theory of natural numbers using the constants 0 and 1, the addition operation + (but not x), and the equality predicate