Re:Theoretical physicist explains why Moore's Law will collapse
by IsTom on Monday April 30, 2012 @02:27PM
(#3910596)
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.
[ Parent
| on HN ]
Re:Theoretical physicist explains why Moore's Law will collapse
by bobbydavid on Monday April 30, 2012 @06:23PM
(#3911880)
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...
Re:Theoretical physicist explains why Moore's Law will collapse
by IsTom on Monday April 30, 2012 @09:12PM
(#3912480)
Undirected 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.