ECCC-Report TR11-060https://eccc.weizmann.ac.il/report/2011/060Comments and Revisions published for TR11-060en-usSat, 16 Apr 2011 12:01:23 +0300
Paper TR11-060
| ReachFewL = ReachUL |
Brady Garvin,
Derrick Stolee,
Raghunath Tewari,
N. V. Vinodchandran
https://eccc.weizmann.ac.il/report/2011/060We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by nondeterministic 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.
Sat, 16 Apr 2011 12:01:23 +0300https://eccc.weizmann.ac.il/report/2011/060