Random-access-machine complexity classes: definitions

This definitions layer places the logarithmic-cost RAM classes over the same Language interface as the Turing-machine classes. It is intentionally independent of either simulation direction.

def Complexity.RAM.DTIME (T : ℕ → ℕ) : Set Language

RAM.DTIME(T) is the class of languages decided by a RAM in logarithmic time O(T(n)).

Equations

• Complexity.RAM.DTIME T = {L : Complexity.Language | ∃ (P : Complexity.RAM.Program) (f : ℕ → ℕ), P.DecidesInTime L f ∧ Complexity.BigO f T}

def Complexity.RAM.DSPACE (S : ℕ → ℕ) : Set Language

RAM.DSPACE(S) is the class of languages decided by a RAM in logarithmic space O(S(n)).

Equations

• Complexity.RAM.DSPACE S = {L : Complexity.Language | ∃ (P : Complexity.RAM.Program) (f : ℕ → ℕ), P.DecidesInSpace L f ∧ Complexity.BigO f S}

def Complexity.RAM.P : Set Language

RAM.P is polynomial logarithmic-cost RAM time.

Equations

• Complexity.RAM.P = ⋃ (k : ℕ), Complexity.RAM.DTIME fun (x : ℕ) => x ^ k