News for hackers. Stuff that matters.

A comment on Theoretical physicist explains why Moore's Law will collapse. Parent comment

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

[ Parent | on HN ]
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.
[ Parent | on HN ]