[EM] Fast Condorcet-Kemeny calculations -- in polynomial time

[Warren Smith]

Fobes:
P does _not_ equal NP -- as far as I know.
Instead, Condorcet-Kemeny calculations are not really NP-hard.

WDS: yes, they are.

Fobes:
If someone claims to have proved that the calculations are NP-hard, they
are standing on thin ice.

WDS: No, they are not.

Fobes:
Yes, a _proof_ that the highest sequence score has been found may be
NP-hard.  Yet, as the calculation descriptions point out, that becomes
an issue only in situations that are like finding the highest sand dune
in a desert.  In such cases different experts will argue about which
candidate really should have won.  More specifically, there will be
arguments about whether Condorcet-Kemeny method results are better than
results from using approval voting or range voting.  In such cases one
meaningful alternative is to declare a tie, and then use whatever
tie-breaking rule (such as a runoff election) is mandated.

WDS:
That entire paragraph was utter garbage and should be disregarded.

(Also, although Fobes speaks in such wacky imprecise ways it is hard
to ever pin him down, it appears he does not understand the
distinction between NP and coNP.)

Fobes:
As for why I have not measured the exact calculation times, they vary.
They depend on the data.

WDS:
exactly what happens generally with NP-hard problems, and bogus proofs
that P=NP like
Fobes'.

Fobes:
As for Warren's wager, no one would (or should) take it.

WDS: bummer.

Fobes: When I was told about the Clay prize I looked into what the
prize was about, I
learned more about NP-hard problems, and I recognized that
Condorcet-Kemeny calculations are _not_ NP-hard.  The problems that are
NP-hard really do require checking every possibility in order to find
the optimum solution.

WDS:
There are plenty of NP-hard problems that do not "require checking
every possibility."
In fact, the definition of "NP" says you only have to check one, the right one.
So Fobes is exactly 100% wrong.

Condorcet Kemeny calculations such as finding the winner, are NP-hard,
despite whatever Fobes has "recognized."   But if you disagree I
suggest contacting
the authors of those papers with your refutations of their proofs.
This would be a small
revolution, not as large as proving P=NP but still significant.
(Except of course,
it won't be, because Fobes's claims are simply bogus.)

NP-hardness was shown in at least 2 published papers, which, unlike
Fobes, contained proofs.  Oddly enough, those authors were not
discouraged by CS being "in its infancy" and actually struggled to
produce a proof, unlike Fobes who simply thinks
good writing is sufficient without any need for careful and precise reasoning,
and figures his intellect is so superior that that kind of mere mental
crutch is not necessary for him.

At one point, it used to be popular for cranks and fools to try to
gain everlasting fame by "squaring the circle," refuting special
relativity, etc.   Nowadays they try to shove
alleged polynomial time algorithms for NP-hard tasks in our face instead.
I just wish people like Fobes would stay away from the voting area and
focus their efforts on cold fusion or alien invaders from Mars or
something instead.  And as I said Fobes does seem to me to have talent
as a writer, so it is sad to see him wasting it by perpetually spewing
his utter garbage and posing as an expert.
    http://en.wikipedia.org/wiki/Crank_(person)

This nonsense also undermines whatever good efforts Fobes might make
in other areas of life.  Supposing he does something good, then people
will say "but he's the crank who proved P=NP" and then a huge cloud
will be cast over everything else Fobes ever accomplishes in his life
(as least as far as 95% of scientists are concerned).
Basically, I now have the view that I automatically disbelieve
everything Fobes ever says, until I get further evidence.













On Wed, Dec 21, 2011 at 5:24 PM, Warren Smith <warren.wds at gmail.com> wrote:
> I have earlier cited published proofs this problem is NP-complete.  If
> Fobes has a
> polynomial time algorithm he has proven P=NP and
> should immediately collect his million dollar Clay Institute prize
> for the greatest mathematical achievement so far this century.
>
> However, I doubt it. I think it far more likely that Fobes is a fraud --
> as has been every other person who has claimed to have invented a
> polytime algorithm for an NP-hard problem
> (and there have been dozens -- they generally serve as a source of amusement for
> computer scientists who enjoy laughing at them).
>
>>Calculating a "complex" case with 12 choices is so fast that
>>I haven't bothered to time the calculations.
>
> --how touching.  Actual computer scientists time their calculations
> versus problem size, however.
>
>>The estimated time for calculating results for 50 choices (!) is less
>>than a minute -- which is far less than a "lifetime".
>
> --quite odd that Fobes had to "estimate" this, why not actually
> spend those few minutes to actually time it?
>
> --Looking at Fobes' so-called descriptions of his so-called algorithms,
> it is rapidly apparent that Fobes blatantly disregards
> and holds in contempt, every computer science paper that has ever presented
> an algorithm before.  Things like "pseudocode" and "proofs"
> evidently are unnecessary for
> a great and revolutionary thinker like Fobes, who instead resorts to
> "English prose poetry-like descriptions" reminiscent of an illustrated
> edition of
> Charles Dickens.
>
> And it all is carefully "copyrighted."
>
> But: might anybody be interested in a little wager?
> If Fobes successfully collects the million dollar Clay Prize by the end of 2012
> for his successful proof P=NP, I
> offer to pay whoever wagers versus me, $10000.
> If not, though, I get the $10000.
>
> Any takers?
>
> --
> Warren D. Smith
> http://RangeVoting.org  <-- add your endorsement (by clicking
> "endorse" as 1st step)



-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html