Re: computer-go: NP-complete problems solved?

[Serge Boisse <boisse@xxxxxxxxxxxx>]

Nick Wedd wrote:
> 
> markus.enzenberger@xxxxxxxxxxxxxxxxx writes
> 
> >I have just seen this article of a Anatoly Plotnikov who
> >claims to have reduced a NP-complete problem to a polynomial
> >algorithm:
> 
> Could "Anatoly Plotnikov" be a Russian "Archimedes Plutonium"?
> 
> Nick
> --
> Nick Wedd    nick@xxxxxxxxxxxxxxxxx

Archimedes plutonium has a monstruous ego that Plotnikov apparently has not.
And AP's only original idea is that natural numbers are p-addics, an idea which
he uses to "solve" well-known conjectures in a way that most mathematicians
(including me) do not agree with...

But Plotnikov'claim is specific to a special P-NP problem, K-cliques
partitioning.

You may be aware that there is a very huge activity in this field, driven by a
$1000,000 prize (see http://www.claymath.org/prize_problems/). so lots of
amateur and professionals are currently claiming to have solved the P/NP
problem. Lot of noise...

Yes, it might be possible that P=NP. wether  Plotnikov's work is a proof of it,
wait and see... For myself, I will check that in depth only when he is published
in a referee journal.

If P=NP, go is a P problem. But what is the "n" used for the determination of
complexity ? is it the size of the board ? if the exposant of n is a huge number
(and it might be), then this doesn't help a lot...

Serge ; http://www.multimania.com/boisse