I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me:

We consider sequence (of polynomial length) of configurations and check if transitions betweens configurations in sequence are legal. We also check if machine accept word $w$. In other words, we analyze run of polynomial-space machine $M$ on word $w$ and check if this run is legal and accepting.

I can't understand why such reasoning work. I don't show exact example because my lecturer use this technique fairly often.

Can you explain me why it work?


1 Answer 1


This technique is also known as computation history method. Given a Turing machine $M$ you (or another TM $M'$) inspect its computation "flow" or "history" configuration by configuration. You can think of TM configuration as snapshot of the tape content plus machine's state at some particular time. Every step of a TM generates a new configuration. The set of all that configurations is a computation history. If computation halts then that set is finite.

UPDATE: (on David Richerby comment) The following paragraph may be irrelevant to the question since I overlooked "sequence (of polynomial length) of configurations" in OP which is different from "the sequence of configurations where each is of polynomial length".

Polynomial length requirement: because you want to prove PSPACE membership, maximum number of used tape cells must be polynomial. That's why an accent made on polynomial length.

Transitions betweens configurations in sequence are legal: you want be sure that machine's transitions between states were really made according to the machines's transition rules, otherwise the run is not legal. For example if a configuration $C_i$ differs from the configuration $C_j$ by 3 symbols (assuming a single tape TM) then you can say that transition is not legal, since the TM cannot change 3 symbols in a single step.

Also note that if one TM $M$ simulates another TM $M'$ then if $M'$ uses polynomial space then the whole simulation also uses polynomial space since simulation itself takes polynomial space.

Example of use of configurations: Assume you know that a certain class of TM machines use no more than, say, $n$ cells of tape where $n$ is input size. Then halting problem for this class of TMs is decidable. Since a TM has finite number of states $|Q|$ and alphabets $|\Sigma|$, and since we that it uses at most $n$ cells, we simply can compute that the TM has at most $n|Q||\Sigma|^n$ configurations. Then you simulate that TM and check if at some point it repeats it's configuration then there must be an infinite loop and so it never halts (since the tape use is bounded!, the TM may not move infinitely move its head to the right and right symbols). The latter class is also known as linear bound automata.

  • $\begingroup$ A polynomial space Turing machine could visit exponentially many configurations before halting (consider, e.g., a machine that counts to $2^n$ in binary and then halts). So it doesn't seem right to restrict to computation sequences of only polynomial length. $\endgroup$ Jul 25, 2017 at 17:32
  • $\begingroup$ @fade2black, David, finally I can' understand your points. is there exists technique as history of computation useful in proving PSPACE-completness ? $\endgroup$ Aug 15, 2017 at 13:49
  • $\begingroup$ @HaskellFun yes, there exists. For example this technique is used in proof of Savitch's theorem, or proof of PSPACE completeness of TQBF problem. $\endgroup$
    – fade2black
    Aug 15, 2017 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.