I've eventually managed to create a problem that should show a full reduction from a Robson problem to Go - I hope is correct.
The Problem: https://drive.google.com/file/d/1tmClDIs-baXUqRC7fQ2iKzMRXoQuGmz2/view?usp=sharing Black just captured in the marked ko. How should White play to save the lower group? > no ko fights and no counting (i.e. first capture) could put this in P. Not true - please read Tromp et al paper: Ladders are PSPACE hard without ko - that is, you can reduce any PSPACE problem in reasonable time to a Go problem without kos. --Marcel On 18 June 2018 at 22:27, uurtamo <uurt...@gmail.com> wrote: > 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 <john.tr...@gmail.com> wrote: >> >> On Mon, Jun 18, 2018 at 10:24 PM, Álvaro Begué <alvaro.be...@gmail.com> >> 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 >> 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
