5 ms·
You can think about decision problems (such that you answer "yes" or "no" to a question) as trying to find a path in (very specific) a graph. UL consists (in a
by IsTom 15y ago
You can think about decision problems (such that you answer "yes" or "no" to a question) as trying to find a path in (very specific) a graph. UL consists (in a hand-waving fashion) of problems that can be stated in such way by undirected graphs of polynomial size. Roughly it means "if I'm in state s and can go to s' I can also go back from s' to s", which is a reversible computation -- reversible processes are not required by thermodynamics to create heat.
- bobbydavid 15y agoIn my experience, UL is "unambiguous log", decision problems that require no more than logarithmic space, and also have a single unique proof (if it exists). It seems like UL-computers would be optimized for finding the path through the maze to the cheese, but log space is a pretty severe restriction...
- IsTom 15y agoUndirected st-connectivity is UL complete (and by showing that it's in L it was shown that UL = L). Logarithmic space is just an arbitrary constraint. It could be polynomial or exp-space.