[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: NP-complete problems solved?
I've forgotten all my complexity theory but there are some things here that
strike me as very odd, and very naive. I would have thought Go to be
EXPTIME, but I'm not sure. Someone stated Go is PSPACE without ko. What are
the rules without ko? It surely isn't Go. And even if Go would be in PSPACE,
solving the P ?= NP question is something different from actually solving
Go. As far as I always had understood, it only says something of the
complexity class of the problem. Problems belonging to the PSPACE class can
still be very, very hard.
Mark Boon