Re: Paper “Complexity of Go” b y Robson

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 <[email protected]> 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 <[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
_______________________________________________
Computer-go mailing list
[email protected]
http://computer-go.org/mailman/listinfo/computer-go