In addition to time, computer scientists also worry about the memory or space that a Turing machine uses. Roughly one can measure space as the number of tape squares used by at Turing machine. We would like to talk about space bounds like log n and still be able to read the whole input so we need a slightly different model.
We now allow our Turing machine to have a read-only input tape, one or more work tapes and for a Turing machine computing a function, a write-only output tape. On the input tape the head can move back and forth but it cannot change the values in any cell. On the output tape the head can only move right, writing as it moves. The amount of space a Turing machine uses on input x is the number of cells of the work tape that it uses. We will assume a space bound of at least log n since we need log n bits to describe the location of the the input head pointer.
In real world terms, think of your computer accessing "the internet". You can still reach many pages even though you cannot store the entire internet on your computer.
Any machine that runs in time t(n) clearly also runs in space t(n). If a machine uses space s(n) and it halts then it will halt in time cs(n) for some constant c. Otherwise the machine will repeat a configuration and run forever.
We define the classes DSPACE(s(n)) as the set of languages that are accepted by Turing machines using at most O(s(n)) space. NSPACE(s(n)) is the same for nondeterministic machine. We will always assume s(n)≥log n and s(n) is an easily computable function.
Common space classes include L=DSPACE(log n), NL=NSPACE(log n), PSPACE=∪kDSPACE(nk) and NPSPACE=∪kNSPACE(nk).
Unlike the P versus NP question, we know quite a bit about the relationship of deterministic versus nondeterministic space through the following two results.
- Savitch's Theorem: NSPACE(s(n))⊆DSPACE(s2(n)). In particular this means NPSPACE = PSPACE.
- Immerman-Szelepcsényi Theorem: If L is in NSPACE(s(n)) then the complement of L is also in NSPACE(s(n)).
No comments:
Post a Comment