Computational Complexity

Wednesday, February 15, 2006

 
Favorite Theorems: Alternation

Posted by Lance

Introduction

Physicists continue to grapple over the relationship of time and space. In computational complexity we settled that question three decades ago: Space is just alternating time.

Chandra, Kozen and Stockmeyer, Alternation, JACM 1981. Based on two 1976 FOCS papers.

An alternating Turing machine is a nondeterministic machine with states marked either existential or universal. Consider a game where player 1 chooses the next legal configuration from existential states and player 2 chooses the next legal configuration from the universal states and player 1 wins if the machine halts in an accept state. The machine accepts those inputs where player 1 has a winning strategy.

Chandra, Kozen and Stockmeyer show

• ATIME(t(n)) ⊆ DSPACE(t(n)) ⊆ NSPACE(t(n)) ⊆ ATIME(t²(n))
• ASPACE(s(n)) = ∪_cDTIME(c^s(n))

Alternation causes a shift in the time-space hierarchy of classes: P = AL, PSPACE = AP, EXP = APSPACE, EXPSPACE = AEXP, etc. More importantly the two fundamental resource bounds of time and space are really just the same concept on different models.

Alternation allows us to show the PSPACE-completeness of many game-based problems. Also alternating machines set the stage for interactive proof systems which led to probabilistically checkable proofs, perhaps the most productive line of research in complexity over the past fifteen years.

The paper also characterizes the polynomial-time hierarchy using bounded alternation and shows that alternating finite automata still accept just regular languages (with a double-exponential blow-up in the number of states).

6:19 AM #

1.  Anonymous says:  
   
   Physicists continue to grapple over the relationship of time and space. In computational complexity we settled that question...
   
   For a moment I thought that you were going to announce some breakthrough on PTIME versus PSPACE, but it seems that it's not entirely true that "we settled that question".
   
   If you want to bond with a physicist, just tell him or her that we too have troubles telling space and time apart.
   
   - Wim van Dam
   

   11:36 AM, February 15, 2006