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

From: Tim May <tcmay.domain.name.hidden>

Date: Mon, 30 Dec 2002 17:35:03 -0800

On Monday, December 30, 2002, at 03:46 AM, Brent Meeker wrote:

*> On 31-Dec-02, Hal Finney wrote:
*

*>
*

*>> One correction, 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, one of the greatest
*

*>> unsolved problems in computability theory.
*

*>
*

*> What about Hamiltonian circuits or factoring an integer or roots of a
*

*> Diophantine equation?
*

Hal will probably answer. I initially had the same reaction you had

(except only about Hamiltonian cycles and roots of Diophantines, but

not factoring, as factoring is not known to be NP-complete).

But upon rereading what Hal wrote, and what I had already drafted a

nearly complete reply to, I saw that he was making the subtle point

that there are "no known problems which take exponential time."

All of the NP-complete problems (Hamiltonian cycle, Diophantine, etc.)

currently only have exponential-time solutions. But there is no

guarantee that a polynomial solution (which is not NP, that is, is not

the result of a "guess" or an "oracle") will not be found sometime in

the future.

Proving that there "are" problems which can only be solved in

exponential time but which can be checked in polynomial time is subtly

different from saying that all problems in the class NP-complete admit

no polynomial time solutions.

(I'm trying to avoid using shorthand like P and NP and Exptime, as a

lot of confusion enters when shorthand gets misinterpreted.)

--Tim May

Received on Mon Dec 30 2002 - 20:37:55 PST

Date: Mon, 30 Dec 2002 17:35:03 -0800

On Monday, December 30, 2002, at 03:46 AM, Brent Meeker wrote:

Hal will probably answer. I initially had the same reaction you had

(except only about Hamiltonian cycles and roots of Diophantines, but

not factoring, as factoring is not known to be NP-complete).

But upon rereading what Hal wrote, and what I had already drafted a

nearly complete reply to, I saw that he was making the subtle point

that there are "no known problems which take exponential time."

All of the NP-complete problems (Hamiltonian cycle, Diophantine, etc.)

currently only have exponential-time solutions. But there is no

guarantee that a polynomial solution (which is not NP, that is, is not

the result of a "guess" or an "oracle") will not be found sometime in

the future.

Proving that there "are" problems which can only be solved in

exponential time but which can be checked in polynomial time is subtly

different from saying that all problems in the class NP-complete admit

no polynomial time solutions.

(I'm trying to avoid using shorthand like P and NP and Exptime, as a

lot of confusion enters when shorthand gets misinterpreted.)

--Tim May

Received on Mon Dec 30 2002 - 20:37:55 PST

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