Re: Paper “Complexity of Go” b y Robson

My understanding: ko fights will take this to (at least, I haven't seen the
EXP argument) PSPACE.

no ko fights and no counting (i.e. first capture) could put this in P.

s.


On Mon, Jun 18, 2018 at 3:21 PM John Tromp <[email protected]> wrote:

> On Mon, Jun 18, 2018 at 10:24 PM, Álvaro Begué <[email protected]>
> wrote:
> > I don't think ko fights have anything to do with this. John Tromp told
> > me that ladders are PSPACE complete: https://tromp.github.io/lad.ps
>
> Ko fights are needed to take Go problems beyond PSPACE.
> For Japanese rules they suffice to go beyond (assuming EXPTIME != PSPACE),
> but for Chinese rules it's an open problem.
>
> regards,
> -John
> _______________________________________________
> Computer-go mailing list
> [email protected]
> http://computer-go.org/mailman/listinfo/computer-go

_______________________________________________
Computer-go mailing list
[email protected]
http://computer-go.org/mailman/listinfo/computer-go