Re: An easy way to prove P != NP

• From: Patricia Shanahan <pats@xxxxxxx>
• Date: Fri, 24 Nov 2006 18:51:28 GMT

Craig Feinstein wrote:
....
A person picks up a puppy in his hands and weighs himself and the puppy
together. Then he weighs himself and subtracts this weight from their
combined weight. This will be the weight of the puppy. This is clearly
the fastest way to weigh one puppy.

But is the fastest way to weigh 10 puppies to repeat this procedure 10
times? No, because the person does not have to weigh himself 10 times.
He only has to weigh himself once and weigh himself with another puppy
10 times.

By the Dynamic Programming Principle that I presented in my paper,
since he is solving each subproblem of getting the weight of each puppy
is the fastest way possible (by weighing himself with the puppy and
also weighing himself) without performing unnecessary work (he
doesn't weigh himself 10 times, which is unnecessary work; he only
weighs himself once), this is the fastest way to get the minimum weight
of the 10 puppies.

Suppose I add the information that nine of the puppies weigh the same,
and one is slightly lighter, not enough so to be visible given all the
squirming. The objective is still to find the weight of the lightest puppy.

How does your argument change?

Patricia
.

Relevant Pages

• Re: For some time now, Ive been trying to find answer....
... weigh in is just insurance. ... they can collect debris in the range of several kilos... ... layer on a tyre that is +70% spaces and guess it's weight. ... It does seem to be exaggerated that collection of debris after the race ...
(rec.autos.sport.f1.moderated)
• Re: Protein grams and portion control??? Pastorio?
... your current weight and body composition, ... "negative calorie" type foods. ... Weigh the cooked whatever before you eat and then weigh the sad, ... I need to weigh the bones prior to doing that. ...
(rec.food.cooking)
• Re: Question about Gatti?
... was some controversy over the weigh in, something to the affect of him ... Both made the weight. ... Which of course bring it up to why not do the weigh in just before the fight ... Controversy against Gamache: ...
(rec.sport.boxing)
• Re: Protein grams and portion control??? Pastorio?
... calorie counts for dietary restriction, do you weigh the meat raw or cooked? ... Depends on the age of the critter when it was killed, although a reasonably normal yield ratio is 46% to 48% of cooked weight, depending on degree of doneness. ... Weigh the cooked whatever before you eat and then weigh the sad, ... Subtract the weight of the formerly living, breathing flesh from the now-murdered, plundered bones. ...
(rec.food.cooking)
• Re: Rolling Resistance
... It's like 1-1/8" headsets and stems and forks (which all weigh more ... the real weight in small print or express it in a fraction of a stone ... Er, yes, but why does a tubeless tire apparently weigh more than the ... tires at ponderous weights. ...
(rec.bicycles.tech)