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

From: Brent Meeker <meekerdb.domain.name.hidden>

Date: Mon, 30 Dec 2002 18:34:53 +0500

On 31-Dec-02, you wrote:

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

OK, you mean that *provably* take exponential time.

...

*>
*

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

It seems it has been proven recently to be in P:

http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html#PRIMES

Brent Meeker

"One cannot guess the real difficulties of a problem before

having solved it."

--- Carl Ludwig Siegel

Received on Mon Dec 30 2002 - 21:35:08 PST

Date: Mon, 30 Dec 2002 18:34:53 +0500

On 31-Dec-02, you wrote:

OK, you mean that *provably* take exponential time.

...

It seems it has been proven recently to be in P:

http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html#PRIMES

Brent Meeker

"One cannot guess the real difficulties of a problem before

having solved it."

--- Carl Ludwig Siegel

Received on Mon Dec 30 2002 - 21:35:08 PST

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