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
Álvaro. On Mon, Jun 18, 2018 at 2:58 PM, uurtamo <uurt...@gmail.com> wrote: > FWIW, first-capture go (i.e. winner is first one to make a capture) should > not be PSPACE-complete. > > the thing in go that makes it hard is ko fights, which don't exist in > capture go. > > s. > > > On Mon, Jun 18, 2018 at 11:55 AM Marcel Crasmaru <crasma...@gmail.com> > wrote: >> >> Errata: > reduction from GO to an EXP hard problem >> >> should be the other way around :) >> >> --Marcel >> >> On 18 June 2018 at 19:36, Marcel Crasmaru <crasma...@gmail.com> wrote: >> >> J. M. Robson (1983) “The Complexity of Go”. Proceedings of the IFIP >> >> Congress 1983 p. 413-417. >> > >> > If you are interested in how to prove that GO with kos and Japanese >> > rules is EXP complete you can get the gist of it from a very early >> > draft of my master thesis >> > - I used Robson's idea of reduction from GO to an EXP hard problem >> > using ladders instead of pipes (he used groups >> > connected through long string of pieces, aka, "pipes") >> > >> > If you have related questions I am happy to answer them although John >> > Tromp might have even better insights - ask him too. >> > >> > Best, >> > Marcel >> > >> > On 18 June 2018 at 17:54, Mario Xerxes Castelán Castro >> > <marioxcc...@yandex.com> wrote: >> >> Hello. I am asking for help finding the following paper: >> >> >> >> J. M. Robson (1983) “The Complexity of Go”. Proceedings of the IFIP >> >> Congress 1983 p. 413-417. >> >> >> >> I could not find it online. There is no DOI anywhere to be found (I >> >> searched Crossref and here: >> >> https://dblp.uni-trier.de/db/conf/ifip/ifip83.html#Robson83 ) and the >> >> conference proceedings are not in Library Genesis either. >> >> >> >> Thanks in advance. >> >> >> >> >> >> _______________________________________________ >> >> Computer-go mailing list >> >> Computer-go@computer-go.org >> >> http://computer-go.org/mailman/listinfo/computer-go >> _______________________________________________ >> Computer-go mailing list >> Computer-go@computer-go.org >> http://computer-go.org/mailman/listinfo/computer-go > > > _______________________________________________ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
