Re: How does the computer tell a live group from a dead group

[Antti Huima <huima@xxxxxx>]

On Thu, 25 Feb 1999, Sam Sloan wrote:

> To those of you who have never actually tried to solve this problem, let me
> tell you that this is not as trivial a problem as it may seem.

It is a PSPACE-hard problem, so it surely is not trivial.  A simple
algorithm exists, in a sense: enumerate the whole remaining game tree and
calculate the game-theoretic liveness value of the group. However, you
don't have enough time for this. On the other hand, PSPACE-hardness shows
that you can't probably do better in the general case. The cases where you
can solve the problem somewhat efficiently are exceptions.

-- 
Antti Huima
SSH Communications Security Oy