[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
computer-go: NP-complete problems solved?
Hello,
I have just seen this article of a Anatoly Plotnikov who
claims to have reduced a NP-complete problem to a polynomial
algorithm:
http://www.geocities.com/st_busygin/clipat.html
Since solving Go is known to be NP-complete and all NP-complete
problems are equivalent, this could have some impact on Computer Go.
Is this the hoax of the year?
Can anyone comment with more knowledge in this area than I have?
- Markus