[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