The Immerman-Szelepcsenyi Theorem
- by Daniel Lorch
In the Immerman-Szelepcsenyi Theorem, two algorithms are specified that use non-determinisim. There is a rather lengthy algorithm using "inductive counting", which determines the number of reachable configurations for a given non-deterministic turing machine. The algorithm looks like this:
Let m_{i+1}=0
For all configurations C
Let b=0, r=0
For all configurations D
Guess a path from I to D in at most i steps
If found
Let r=r+1
If D=C or D goes to C in 1 step
Let b=1
If r<m_i halt and reject
Let m_{i+1}=m_{i+1}+b
I is the starting configuration.
m_i is the number of configurations reachable from the starting configuration in i steps. This algorithm only calculates the "next step", i.e. m_i+1 from m_i. This seems pretty reasonable, but since we have nondeterminisim, why don't we just write:
Let m_i = 0
For all configurations C
Guess a path from I to C in at most i steps
If found
m_i = m_i + 1
What is wrong with this algorithm?
I am using nondeterminism to guess a path from I to C, and I verify reachability
I am iterating through the list of ALL configurations, so I am sure to not miss any configuration
I respect space bounds
I can generate a certificate (the list of reachable configs)
I believe I have a misunderstanding of the "power" of non-determinisim, but I can't figure out where to look next. I am stuck on this for quite a while and I would really appreciate any help.
