Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-060 | 15th April 2011 23:57

ReachFewL = ReachUL

RSS-Feed




TR11-060
Authors: Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran
Publication: 16th April 2011 12:01
Downloads: 4318
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint