Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BRADY GARVIN:
All reports by Author Brady Garvin:

TR11-060 | 15th April 2011
Brady Garvin, Derrick Stolee, Raghunath Tewari, Vinodchandran Variyam

ReachFewL = ReachUL

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




ISSN 1433-8092 | Imprint