Alternation Turing Machines

Outline

Nondeterministic Turing Machines

Alternation

ATIME and ASPACE

\(Σ\)_i-alternating Turing Machines and \(Π\)_i-alternating Turing Machines

Nondeterministic Turing Machines

Basic Idea

Deterministic Finite Automata → Nondeterministic Finite Automata

Basic Idea

Deterministic Finite Automata → Nondeterministic Finite Automata

Turing Machine → ?

Basic Idea

Deterministic Finite Automata → Nondeterministic Finite Automata

Turing Machine → Nondeterministic Turing Machine

Basic Idea

Deterministic Finite Automata → Nondeterministic Finite Automata

Turing Machine → Nondeterministic Turing Machine

P → NP

Formal Description

\(M = (Q,Σ,ι,\_,A,δ) \)

$Q$ is the set of states

$Σ$ is the Tape Alphabet

$ι$ is the initial state: $ι ∈ Q$

$\_$ is the blank symbol: $\_ ∈ Σ$

$A$ is the set of accept states: $A ∈ Q$

$δ$ is the transition function: $δ ⊂ (Q \backslash A x Σ) → P(Q x Σ x \{L,R\})$

Example: SAT

Assign all possible assignments of variables concurrently

Check if any of them evaluate to true… concurrently!

If you find one that does, accept!

Alternation

Basic Idea

NTMs are kinda… easy to please?

Basic Idea

NTMs are kinda… easy to please?

All states are logical “or’s”

Basic Idea

How about we have a system where we could have alternating or’s and and’s?

Basic Idea

Basic Idea

Turing Machines → Nondeterministic Turing Machines → Alternating Turing Machines

P → NP → AP

Formal Description

\(M = (Q,Γ,δ,q₀,g)\)

$Q$ is the still set of states

$Γ$ is now the Tape Alphabet

$δ$ is still the transition function: $δ : (Q x Σ) → P(Q x Γ x \{L,R\})$

$q₀$ is now the initial state: $q₀ ∈ Q$

$g$ is a function that specifies the type of each state $g : Q → \{∧,∨,accept,reject\}$

Examples: TAUT (Tautology)

$TAUT = \{\langle Φ \rangle | Φ$ is a tautology$\}$ Universally select all possible assignments to the variables of $Φ$ ($∧$) Evaluate these assignments to see if they are true If all the assignments accept, accept! Otherwise… reject!

Examples: SEXY

L = \{S | S is a series of 1’s in a positive multiple of 3, followed by an even amount of 0’s, or the inverse (3x 0’s followed by 2y 1’s)\}

Spent a lot of time on this one!

Not exactly a particularly difficult problem to solve anyhow, but…

Examples: MIN-FORMULA

$MIN-FORMULA = \{\langle Φ \rangle | Φ$ is the smallest possible way to express that formula$\}$

Universally select all formulas $ψ$ that are shorter than $Φ$ ($∧$)

Existentially select an assignment to the variables of $Φ$ ($∨$)

Evaluate both $Φ$ and $ψ$, accept if they have the same values, otherwise reject!

ATIME and ASPACE

TIME and (Relative Dimension In) SPACE

ATIME and ASPACE (ATARDIAS?)

$ATIME(t(n)) = \{L|L$ is decided by an $O(t(n))$ time alternating Turing Machine $\}$

$ASPACE(f(n)) = \{L|L$ is decided by an $O(f(n))$ space alternating Turing Machine $\}$

Relations!

For $f(n) ≥ n$, we have $ATIME(f(n)) \subseteq SPACE(f(n)) \subseteq ATIME(f²(n))$

For $f(n) ≥ log n$, we have $ASPACE(f(n)) = TIME(2^O(f(n)))$

\(Σ\)_i-alternating Turing Machines and \(Π\)_i-alternating Turing Machines

Definitions

$Σ_i$-alternating Turing machine is an alternating Turing machine that on the longest possible branch has $i runs$ universal or existential steps

$Σ_i$-alternating Turing machines start with existential steps

$Π_i$-alternating Turing machines start with universal steps

\(Σ\)_iTIME, \(Π\)_iTIME, \(Σ\)_iSPACE, \(Π\)_iSPACE

…Not hard to figure out what all these are

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

$Σ₁P$

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

$NP = Σ₁P$

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

$NP = Σ₁P$

$coNP = Π₁P$

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

$NP = Σ₁P$

$coNP = Π₁P$

$MIN-FORMULA ∈ Π₂P$

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

$NP = Σ₁P$

$coNP = Π₁P$

$MIN-FORMULA ∈ Π₂P$

$SEXY ∈ Σ₃P$

\(Σ_iP\) and \(Π _iP\)

$Σ_iP = ∪_{k ∈ \Re} Σ_iTIME(n^k)$

$Π_iP = ∪_{k ∈ \Re} Π_iTIME(n^k)$

$NP = Σ₁P$

$coNP = Π₁P$

$MIN-FORMULA ∈ Π₂P$

$SEXY ∈ Σ₃P$

(It is also most definitely in P)

Conclusion