# 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.