3 ms·
In 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). I
by bobbydavid 14y ago
In 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 14y 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.