An easy way to prove P != NP

Take the following NP problem:

Modified Traveling Salesman Problem - A traveling salesman starts at
city 1, travels to cities 2,...,n-1 in any order that the salesman
chooses, and then ends his trip in city n. Let us denote d(i,j) to be
the distance from city i to city j. The goal of the Modified Traveling
Salesman problem is to minimize the total distance traveled by the
traveling salesman.

For any nonempty subset S of {2,...,n} and for any city i in S, let
Opt[S;i] be the length of the shortest path which starts at city 1,
visits all cities in S-{i} and finally stops at city i. Clearly,
Opt[{i};i]=d(1,i) and

Opt[S;i] = min { Opt[S-{i};j] + d(j,i) : j in S-{i} }.

So the Modified Traveling Salesman problem is equivalent to computing
Opt[{2,...,n};n]. It is possible to prove by induction on n that there
is no faster way (in the worst-case scenario) to compute
Opt[{2,...,n};n] than to apply this formula recursively, saving the
value of Opt[S;i] for each subset S in {2,...,n} and each i in S at
each step in the recursion, if one is to assume the following:

The Dynamic Programming Principle - If a problem is equivalent to a
function of more than one independent subproblems and some algorithm A
solves each of the subproblems in the minimum running-time possible (in
the worst case scenario) without performing unnecessary or redundant
calculations and then computes the function of the subproblems to solve
the problem, then there is no algorithm with a faster running-time (in
the worst case scenario) than algorithm A for solving the problem.

Such a recursive procedure described above for solving the Modified TSP
conforms to the Dynamic Programming Principle, because the subproblems
of determining the values of each Opt[S-{i};j] + d(j,i) for each j in
S-{i} are independent from one another in the sense that the value of
each d(j,i) for each j in S-{i} is input for one and only one of the
subproblems and also there are no unnecessary or redundant calculations
performed since the values of Opt[S;i] for each subset S in {2,...,n}
and each i in S are saved at each step in the recursion procedure.
Since such a procedure takes exponential time (on the order of 2^n
times of polynomial of n), and the Modified Traveling Salesman problem
is in NP, we can conclude that P!=NP.

The above recursive procedure is really a form of the Held-Karp
algorithm invented in the 1960's. No deterministic and exact procedure
with a better worst-case time has ever been found since then for
Traveling Salesman-type problems, because it is impossible for such a
procedure to exist.

Craig

> Such a recursive procedure described above for solving the Modified TSP
> conforms to the Dynamic Programming Principle, because the subproblems
> of determining the values of each Opt[S-{i};j] + d(j,i) for each j in
> S-{i} are independent from one another in the sense that the value of
> each d(j,i) for each j in S-{i} is input for one and only one of the
> subproblems and also there are no unnecessary or redundant calculations
> performed since the values of Opt[S;i] for each subset S in {2,...,n}
> and each i in S are saved at each step in the recursion procedure.

But you haven't shown how the procedure solves the problem "in the
minimum running-time possible (in the worst case scenario)".

eKo1 wrote:
> > Such a recursive procedure described above for solving the Modified TSP
> > conforms to the Dynamic Programming Principle, because the subproblems
> > of determining the values of each Opt[S-{i};j] + d(j,i) for each j in
> > S-{i} are independent from one another in the sense that the value of
> > each d(j,i) for each j in S-{i} is input for one and only one of the
> > subproblems and also there are no unnecessary or redundant calculations
> > performed since the values of Opt[S;i] for each subset S in {2,...,n}
> > and each i in S are saved at each step in the recursion procedure.
>
> But you haven't shown how the procedure solves the problem "in the
> minimum running-time possible (in the worst case scenario)".

We can easily use induction on n to prove this. It's trivially true for
n=2, since Opt({2};2)=d(1,2), so one just has to output the value of
d(1,2) to solve the problem for n=2, clearly the fastest algorithm.
Assume true for n=k and prove true of n=k+1 using the Dynamic
Programming Principle to show that such a recursive procedure has the
best worst-case running-time of all deterministic and exact procedures
that solve the modified TSP. It follows that P != NP.

Craig

> We can easily use induction on n to prove this. It's trivially true for
> n=2, since Opt({2};2)=d(1,2), so one just has to output the value of
> d(1,2) to solve the problem for n=2, clearly the fastest algorithm.
> Assume true for n=k and prove true of n=k+1 using the Dynamic
> Programming Principle to show that such a recursive procedure has the
> best worst-case running-time of all deterministic and exact procedures
> that solve the modified TSP. It follows that P != NP.

I would not call your procedure "the fastest algorithm" because it
isn't really an algorithm. For some reason, I'm not satisfied with that
inductive proof. Would you show, using proof by contradiction, that
your procedure is the "fastest"?

On 2 Nov 2006 12:34:20 -0800, "Craig Feinstein" <cafeinst{}msn.com>
wrote:

>
>eKo1 wrote:
>> > Such a recursive procedure described above for solving the Modified TSP
>> > conforms to the Dynamic Programming Principle, because the subproblems
>> > of determining the values of each Opt[S-{i};j] + d(j,i) for each j in
>> > S-{i} are independent from one another in the sense that the value of
>> > each d(j,i) for each j in S-{i} is input for one and only one of the
>> > subproblems and also there are no unnecessary or redundant calculations
>> > performed since the values of Opt[S;i] for each subset S in {2,...,n}
>> > and each i in S are saved at each step in the recursion procedure.
>>
>> But you haven't shown how the procedure solves the problem "in the
>> minimum running-time possible (in the worst case scenario)".
>
>We can easily use induction on n to prove this. It's trivially true for
>n=2, since Opt({2};2)=d(1,2), so one just has to output the value of
>d(1,2) to solve the problem for n=2, clearly the fastest algorithm.
>Assume true for n=k and prove true of n=k+1 using the Dynamic
>Programming Principle to show that such a recursive procedure has the
>best worst-case running-time of all deterministic and exact procedures
>that solve the modified TSP. It follows that P != NP.
>
>Craig


CONGRATULATIONS!

A.L.

eKo1 wrote:
> Craig Feinstein wrote:
> [...]
> > We can easily use induction on n to prove this. It's trivially true for
> > n=2, since Opt({2};2)=d(1,2), so one just has to output the value of
> > d(1,2) to solve the problem for n=2, clearly the fastest algorithm.
> > Assume true for n=k and prove true of n=k+1 using the Dynamic
> > Programming Principle to show that such a recursive procedure has the
> > best worst-case running-time of all deterministic and exact procedures
> > that solve the modified TSP. It follows that P != NP.
>
> I would not call your procedure "the fastest algorithm" because it
> isn't really an algorithm. For some reason, I'm not satisfied with that
> inductive proof. Would you show, using proof by contradiction, that
> your procedure is the "fastest"?

Craig Feinstein is known for his "the definition is the only way to
arrive at the result" arguments. He used a similar one to show that any
proof of the Collatz (3x+1) Conjecture must calculate the kth iteration
of n, for all n, and hence take up an infinite amount of space. This
argument has been discredited, partially because it leads to false
results in similar situations, but Feinstein still thinks he's proven
that one, too. Feinstein also doesn't take induction into consideration
in his definition of a proof in his 3x+1 paper.

--- Christopher Heckman

Hi,



Well - it is not complicated to show that the:
>>> minimum running-time possible (in the worst case scenario).

can be faster.



Imagine instance for n=100 where all weights are equal to 100. We can give
answer that optimal tour is 10^4 in O(n^2) steps (time required to check
that all weights are equal). Or if all weights are equal 100 but from xi to
xi+1 weight is equal to 1. Such instances type may also be solved in O(n^2).



Claim that showed method is fastest is then FALSE for above instances, what
means "it is not true always", so it is not proof that always P!=NP.
Building such proof is much more complicated (my attempt uses lots of
abstract math and takes 50 pages).



So, presented lower bound estimation is correct, but for method. It is not
LB for TSP problem.



Getting back to "Modified TSP problem". As far as I remember definition of P
and NP class it consists of decision problems (YES/NO answer) - the goal is
to answer "is there possible tour of overall weight X". Finding optimal
solution is one of possible ways to answer question when X is to be
optimal... But to provide answer YES/NO we do not have to follow certain
procedure. You might even have guessed answer (this would be hard to prove
that is always correct) but time required is O(1) .



Cheers,



Radek Hofman






Uzytkownik "A.L." <alewando{}fala2005.com> napisal w wiadomosci
news:mapkk2tk5r7oo5968dv6vt3h52v68g96qg{}4ax.com.. .
> On 2 Nov 2006 12:34:20 -0800, "Craig Feinstein" <cafeinst{}msn.com>
> wrote:
>
>>
>>eKo1 wrote:
>>> > Such a recursive procedure described above for solving the Modified
>>> > TSP
>>> > conforms to the Dynamic Programming Principle, because the subproblems
>>> > of determining the values of each Opt[S-{i};j] + d(j,i) for each j in
>>> > S-{i} are independent from one another in the sense that the value of
>>> > each d(j,i) for each j in S-{i} is input for one and only one of the
>>> > subproblems and also there are no unnecessary or redundant
>>> > calculations
>>> > performed since the values of Opt[S;i] for each subset S in {2,...,n}
>>> > and each i in S are saved at each step in the recursion procedure.
>>>
>>> But you haven't shown how the procedure solves the problem "in the
>>> minimum running-time possible (in the worst case scenario)".
>>
>>We can easily use induction on n to prove this. It's trivially true for
>>n=2, since Opt({2};2)=d(1,2), so one just has to output the value of
>>d(1,2) to solve the problem for n=2, clearly the fastest algorithm.
>>Assume true for n=k and prove true of n=k+1 using the Dynamic
>>Programming Principle to show that such a recursive procedure has the
>>best worst-case running-time of all deterministic and exact procedures
>>that solve the modified TSP. It follows that P != NP.
>>
>>Craig
>
>
> CONGRATULATIONS!
>
> A.L.

Radoslaw Hofman wrote:
> Hi,
>
> Well - it is not complicated to show that the:
> >>> minimum running-time possible (in the worst case scenario).
>
> can be faster.
>
> Imagine instance for n=100 where all weights are equal to 100. We can give
> answer that optimal tour is 10^4 in O(n^2) steps (time required to check
> that all weights are equal). Or if all weights are equal 100 but from xi to
> xi+1 weight is equal to 1. Such instances type may also be solved in O(n^2).

Hi!

Its obvious to me, from many posts over the past month, you have a much
stronger grasp on this problem than, well, quite a lot of people. But
to my untrained eye (and I stress "untrained"), it looks like this
example you give fails.

to wit:
>>If a problem is equivalent to a
>>function of more than one independent subproblems and some algorithm A
>>solves each of the subproblems in the minimum running-time possible (in
>>the worst case scenario)

Isn't the instances here n=1,n=2,...? If so you can't specify weights
at the the instance level.

It _looks_ like if the instances are any more specific you're not
talking about TSP (or for that matter even an NP problem).

So ... probably I'm confused about something, very trivial. What am I
not understanding?

mathisart wrote:
> Radoslaw Hofman wrote:
> > Hi,
> >
> > Well - it is not complicated to show that the:
> > >>> minimum running-time possible (in the worst case scenario).
> >
> > can be faster.
> >
> > Imagine instance for n=100 where all weights are equal to 100. We can give
> > answer that optimal tour is 10^4 in O(n^2) steps (time required to check
> > that all weights are equal). Or if all weights are equal 100 but from xi to
> > xi+1 weight is equal to 1. Such instances type may also be solved in O(n^2).
>
> Hi!
>
> Its obvious to me, from many posts over the past month, you have a much
> stronger grasp on this problem than, well, quite a lot of people. But
> to my untrained eye (and I stress "untrained"), it looks like this
> example you give fails.
>
> to wit:
> >>If a problem is equivalent to a
> >>function of more than one independent subproblems and some algorithm A
> >>solves each of the subproblems in the minimum running-time possible (in
> >>the worst case scenario)
>
> Isn't the instances here n=1,n=2,...? If so you can't specify weights
> at the the instance level.
>
> It _looks_ like if the instances are any more specific you're not
> talking about TSP (or for that matter even an NP problem).
>
> So ... probably I'm confused about something, very trivial. What am I
> not understanding?

The fact is that it has been an open problem (until yesterday when I
posted this thread) whether there is a faster (in the worst-case
scenario) deterministic and exact algorithm for solving the Modified
Traveling Salesman problem than the Held-Karp algorithm - see the
beginning of section 2 of the following paper:
www.win.tue.nl/~gwoegi/CO2a/exact2.pdf

The reason why nobody came up with the very trivial argument that I
posted in this thread yesterday a long time ago is precisely because
P!=NP. P!=NP means that it is possible for very smart people to be
completely baffled by problems which have trivial solutions. And the P
vs. NP problem ironically is one of these problems which has a trivial
solution.

It doesn't matter how smart you are. There are certain problems which
it is impossible for the smartest people in the world to solve, yet
even children can understand the solutions to such problems. So what
should we do when such problems come up in life? The answer comes from
modern day theory complexity theory - you need oracles to solve such
problems. It is well known that P=NP relative to certain oracles. But
oracles are not realistic solutions to such problems, right?

Not necessarily. God fits the complexity theory definition of an
oracle. So in order to solve the difficult problems which inevitably
come up in life, modern computational complexity theory demonstrates
that the best strategy is to turn to God for the answer.

Craig

Craig Feinstein wrote:
> mathisart wrote:
> > Radoslaw Hofman wrote:
> > > Hi,
> > >
> > > Well - it is not complicated to show that the:
> > > >>> minimum running-time possible (in the worst case scenario).
> > >
> > > can be faster.
> > >
> > > Imagine instance for n=100 where all weights are equal to 100. We can give
> > > answer that optimal tour is 10^4 in O(n^2) steps (time required to check
> > > that all weights are equal). Or if all weights are equal 100 but from xi to
> > > xi+1 weight is equal to 1. Such instances type may also be solved in O(n^2).
> >
> > Hi!
> >
> > Its obvious to me, from many posts over the past month, you have a much
> > stronger grasp on this problem than, well, quite a lot of people. But
> > to my untrained eye (and I stress "untrained"), it looks like this
> > example you give fails.
> >
> > to wit:
> > >>If a problem is equivalent to a
> > >>function of more than one independent subproblems and some algorithm A
> > >>solves each of the subproblems in the minimum running-time possible (in
> > >>the worst case scenario)
> >
> > Isn't the instances here n=1,n=2,...? If so you can't specify weights
> > at the the instance level.
> >
> > It _looks_ like if the instances are any more specific you're not
> > talking about TSP (or for that matter even an NP problem).
> >
> > So ... probably I'm confused about something, very trivial. What am I
> > not understanding?
>
> The fact is that it has been an open problem (until yesterday when I
> posted this thread) whether there is a faster (in the worst-case
> scenario) deterministic and exact algorithm for solving the Modified
> Traveling Salesman problem than the Held-Karp algorithm - see the
> beginning of section 2 of the following paper:
> www.win.tue.nl/~gwoegi/CO2a/exact2.pdf
>
> The reason why nobody came up with the very trivial argument that I
> posted in this thread yesterday a long time ago is precisely because
> P!=NP.

There can't be a trivial argument, one way or another. Someone else
would have found it thirty years ago, and we wouldn't be having this
discussion.

OTOH, if Craig thinks he's found a trivial argument, he'd better write
it up and send it to a refereed journal before I do.

> P!=NP means that it is possible for very smart people to be
> completely baffled by problems which have trivial solutions. And the P
> vs. NP problem ironically is one of these problems which has a trivial
> solution.
>
> It doesn't matter how smart you are. There are certain problems which
> it is impossible for the smartest people in the world to solve, yet
> even children can understand the solutions to such problems.

So _finding_ solutions is harder than _verifying_ solutions. Duh.

> So what
> should we do when such problems come up in life? The answer comes from
> modern day theory complexity theory - you need oracles to solve such
> problems. It is well known that P=NP relative to certain oracles. But
> oracles are not realistic solutions to such problems, right?

((Shake, shake, shake)) "Reply hazy, try again". ((Shake, shake,
shake)) "Better not tell you now".

> Not necessarily. God fits the complexity theory definition of an
> oracle. So in order to solve the difficult problems which inevitably
> come up in life, modern computational complexity theory demonstrates
> that the best strategy is to turn to God for the answer.

Define "God".

--- Christopher Heckman