4 ms·

Long live the UL-class computations!

• DennisP 15y ago
  I googled but didn't find anything I understood. Can you explain without giving a course in computation theory?
  • 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 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 15y ago
        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.