Not all functions f(n) are good ones for time or space bounds. A time or space bound function should not take a long time or a lot of space to compute.
Definition. Function f(n) is time-honest if f(n) can be computed within O(f(n)) time.
Definition. Function f(n) is space-honest if f(n) can be computed within O(f(n)) space.
Simple bounds like n2 are computable very easily. All of the typical time or space functions that we use are both time-honest and space-honest.
A function f(n) that is (probably) not time-honest is: if n is prime, f(n) = n2. If n is composite, f(n) = n.
We need to look at space classes defined in terms of nondeterministic algorithms.
Definition. NSPACE(f(n)) is the class of all decision problems that can be solved by nondeterministic algorithms using space O(f(n)).
Remember that the space bound only applies to the evidence checker.
The definition of nondeterministic algorithms based on evidence checking is correct, but it is not the original definition of nondeterminism.
A nondeterministic Turing machine is just like a deterministic Turing machine except that, in a given state, with a given character under the tape head, the program can do more than one thing.
That is equivalent to having a branch construct in a programming language, where
branch
A
with
B
end branch
can do either A or B. The choice is not made at random.
Rather, both branches are possible things that the program
could do.
We say that a nondeterministic program accepts input x if there exist choices that can be made at the branch points that lead the program to return true.
This definition of nondeterministic algorithms is equivalent to the definition that is based on evidence checking.
The evidence is a string of 0's and 1's, with the first bit telling which choice the first branch should make, the second bit telling which choice the second branch should make, etc.
The checker is the nondeterministic program. Just run it, using the choices indicated by the evidence. If the program returns true, then accept the evidence as good evidence.
At any given moment, a Turing machine is in a particular configuration described by what is on the tape, where the head is, and which state the machine is in. (You can think of the state as an instruction number, telling the next instruction that the program is about to perform.)
Recall that a Turing machine starts with the input written on the tape, followed by infinitely many blank symbols. To describe what is on the tape, we only need to write down that part up to the last nonblank character; everything after that is assumed to be blank.
A convenient way to show a configuration is to write the contents of the tape up to the last nonblank character, with the state written inside it just before the position where the head is.
For example, the start configuration on input x is q0x, where q0 is the start state (the beginning of the program).
Given a nondeterministic Turing machine M, it is easy to modify M as follows.
When M is about to accept, it writes a blank in every cell of the tape, moves the head to the left end of the tape, and enters a particular state accepting state qf.
In state qf, rather than stopping and accepting, it loops forever, staying in state qf, and not moving the tape head or writing on the tape.
Call a machine that behaves like that a clearing Turing machine.
Put briefly, a clearing Turing machine accepts by entering configuration qf and sitting there forever.
A computation of nondeterministic Turing machine N is a sequence of configurations, where each step from one configuration to the next is a possible step of N.
The length of a computation is the number of steps that it makes, which is one more than the number of configurations.
A nondeterministic Turing machine can have many computations: if c is a configuration, then there might be two configurations, c1 and c2, that can follow c.
Let N be a nondeterministic Turing machine. The reachability problem for N is as follows.
Input. Two configurations c1 and c2 of N, a nonnegative integer t and a positive integer s.
Question. Does there exist a computation of N that
The following recursive algorithm solves the reachability problem for a particular nondeterministic Turing machine N.
reachable(c1, c2, t, s)
if t = 0 then
if c2 can follow c1 in one step of N
then return true
else return false
end if
else
For all configurations c3 with s tape cells
if reachable(c1, c3, t−1, s) and
reachable(c3, c2, t−1, s)
then return true
end if
end for
return false
end if
The time for this algorithm is very high. But what about space?
Space is reusable. The key observation is that the two recursive reachable computations can use the same memory.
Each frame for reachable needs space s to write down configuration c3. There are at most t+1 frames in existence at any given time.
(Let T be the initial value of t passed to reachable. The initial call to reachable calls reachable with t = T−1, which calls reachable with t = T−2, etc. down to the last frame with t = 0.)
So the total space needed is s⋅t.
It is conjectured that P ≠ NP. That is, nondeterministic polynomial time is much more powerful than deterministic polynomial time. But space is diffeent.
Savitch's Theorem. Suppose that f(n) is a space-honest function.
NSPACE(f(n)) ⊆ SPACE(f(n)2).
Proof. Suppose that N is an arbitrary nondeterministic Turing machine that runs within space O(f(n)). We need to find a deterministic Turing machine M that accepts exactly the same inputs as N, and that runs within space f(n)2.
Since N uses only O(f(n)) space, there must be a constant d so that N uses only O(d f(n)) time.
We can assume that N is a clearing Turing machine. So there is a constant d so that, if N accepts input x, then it is possible to start N in configuration q0x and reach configuration qf in exactly d f(n) steps.
But d f(n) = 2log(d)f(n), where the logarithm is base 2.
So deterministic machine M just needs to solve the reachability problem with initial configuration q0x, final configuration qf and t = log(d)f(n), and s = f(n).
We saw above that M only needs space s⋅t = log(d)f(n)2, which is O(f(n)2).
Define NPSPACE to be the class of all decision problems that can be solved nondeterministically in polynomial space.
Since converting a nondeterministic machine to a deterministic machine only squares the space, it is clear that NPSPACE = PSPACE.
So we refer to the class as PSPACE.
The proof of Savitch's theorem above needs a space-honest function f(n). That is because the first step of the deterministic machine M involves computing f(n), and M must not violate its space bound in that step.
But a little more thought shows that the honesty requirement is not really needed. I will leave that to Sipser. See the discussion at the end of the proof of Savitch's theorem.