Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Favorite Theorems: Alternation

Expand Messages
  • Lance
    Introduction Physicists continue to grapple over the relationship of time and space. In computational complexity we settled that question three decades ago:
    Message 1 of 1 , Feb 15, 2006
      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(t2(n))
      • ASPACE(s(n)) = ∪cDTIME(cs(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).

      --
      Posted by Lance to Computational Complexity at 2/15/2006 06:19:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.