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

From: Hal Finney <hal.domain.name.hidden>

Date: Mon, 30 Dec 2002 17:23:52 -0800

Hans Moravec writes:

*> 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)
*

I'm not sure if you are disagreeing with either of my statements above,

that (1) there are no known problems which take exponential time but

which can be checked in polynomial time, or that (2) if such a problem

could be found it would prove that P != NP.

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

As I understand the state of play, factoring into primes is not known

to be NP-complete, but the contrary is not known, either. Factoring is

strongly suspected not to be NP-complete but that has not been proven.

So it is still possible that factoring into primes is just as hard as

the TSP, although it is thought to be unlikely (it would imply that

NP = coNP).

Hal Finney

Received on Mon Dec 30 2002 - 20:25:04 PST

Date: Mon, 30 Dec 2002 17:23:52 -0800

Hans Moravec writes:

I'm not sure if you are disagreeing with either of my statements above,

that (1) there are no known problems which take exponential time but

which can be checked in polynomial time, or that (2) if such a problem

could be found it would prove that P != NP.

As I understand the state of play, factoring into primes is not known

to be NP-complete, but the contrary is not known, either. Factoring is

strongly suspected not to be NP-complete but that has not been proven.

So it is still possible that factoring into primes is just as hard as

the TSP, although it is thought to be unlikely (it would imply that

NP = coNP).

Hal Finney

Received on Mon Dec 30 2002 - 20:25:04 PST

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