[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: Two ways to program a GO-engine
From: Thomas Johnson
>> This is one occasion when it is useful to call on the theoretical result,
>> that Go is NP complete. Therefore there cannot be this sort of hidden
>> secret, valid on boards of all sizes, depending only on computation
linear
>> in the board size.
>
>I wouldn't say "cannot". Just because something's NP complete doesn't mean
it
>can't be done in polynomial time. It just means that we don't "know" if it
>can. From what we've seen so far, NP complete problems seem to be
exponential.
>But nobody's proven it - either way.
Yes, I should have said NP-hard, and qualified with the conjecture that P
isn't NP.
Charles