- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Hans Moravec <hpm.domain.name.hidden>

Date: Mon, 30 Dec 2002 19:28:28 -0500

Hal Finney:

*> there are no known problems which take
*

*> exponential time but which can be checked
*

*> in polynomial time. If such a problem could
*

*> be found it would prove that P != NP ...
*

Communications glitch here. The definition

of NP is problems that can be solved in

polynomial time on a "nondeterministic"

machine, that is one that can test

simultaneously all candidate solutions

(effectively by creating exponentially

many processes for testing all possible

combinations of undetermined variables,

each individual combination taking polynomial

time to check)

A favorite example is the traveling

salesman problem (TSP), stated as "There is

a cycle of length no greater than L that

passes through all N nodes of this graph

exactly once." (True or False)

There are exponentially (in N) many cycles,

so determining if any one of them has

length less than L would seem to require

exponential time (barring some yet-

undiscovered P=NP trick)

But if an exponential solution finder

also returns, when it answers "True", a

cycle it found that had length <=L, that

answer can be checked in linear time: just

add up the arc distances.

It is conceivable that an efficient TSP

solver could correctly return "Yes" for a

given L without being able to identify a

winning cycle.

Checking that answer would then be no easier

than solving the original problem.

By the way, it is known that factoring into

primes is easier than the TSP. The discovery

of a classical polynomial time algorithm for

factoring would cause much less shock than

one for the TSP (which is "NP-complete",

the hardest class of NP problems. A polynomial

solution for any NP-complete problem can

be mapped into a polynomial solution for all

NP-complete problems, and thus all NP problems,

and factoring).

Received on Mon Dec 30 2002 - 19:33:04 PST

Date: Mon, 30 Dec 2002 19:28:28 -0500

Hal Finney:

Communications glitch here. The definition

of NP is problems that can be solved in

polynomial time on a "nondeterministic"

machine, that is one that can test

simultaneously all candidate solutions

(effectively by creating exponentially

many processes for testing all possible

combinations of undetermined variables,

each individual combination taking polynomial

time to check)

A favorite example is the traveling

salesman problem (TSP), stated as "There is

a cycle of length no greater than L that

passes through all N nodes of this graph

exactly once." (True or False)

There are exponentially (in N) many cycles,

so determining if any one of them has

length less than L would seem to require

exponential time (barring some yet-

undiscovered P=NP trick)

But if an exponential solution finder

also returns, when it answers "True", a

cycle it found that had length <=L, that

answer can be checked in linear time: just

add up the arc distances.

It is conceivable that an efficient TSP

solver could correctly return "Yes" for a

given L without being able to identify a

winning cycle.

Checking that answer would then be no easier

than solving the original problem.

By the way, it is known that factoring into

primes is easier than the TSP. The discovery

of a classical polynomial time algorithm for

factoring would cause much less shock than

one for the TSP (which is "NP-complete",

the hardest class of NP problems. A polynomial

solution for any NP-complete problem can

be mapped into a polynomial solution for all

NP-complete problems, and thus all NP problems,

and factoring).

Received on Mon Dec 30 2002 - 19:33:04 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*