ReachFewL = ReachUL

摘要

We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by non-deterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the class of problems decided by nondeterministic log-space machines which on every input have at most polynomially many computation paths from the start configuration to any other configuration. We show that ReachFewL = ReachUL.