Re: Factoring integers on a classical computer

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 03/16/05 

Date: Wed, 16 Mar 2005 18:36:03 +0000 (UTC)

There is a better argument why factoring (or its associated decision
problem) is considered "unlikely" to be NP-complete.

Factoring is known to be in NP intersect co-NP. If factoring were
NP-complete, then we would have NP = co-NP. The latter is not known
to be true, and many would consider it to be a surprise if NP = co-NP
(in the same way that many would be surprised if P = NP).

Relevant Pages

  • Re: Factoring integers on a classical computer
    ... problem) is considered "unlikely" to be NP-complete. ... Factoring is known to be in NP intersect co-NP. ... and many would consider it to be a surprise if NP = co-NP ...
    (comp.theory)
  • Re: The factoring problem
    ... ""unlikely"" to be NP-complete, for the following reason. ... Factoring is known to be in NP intersect co-NP. ...
    (sci.crypt)
  • Re: 1M prize P, NP and factorization and other invaluable things
    ... decision problems. ... Factoring is known NOT to be ... factoring can not be NP-hard if P!= NP; ... either P or NP-complete. ...
    (sci.crypt)
  • Re: Factoring integers on a classical computer
    ... Factoring is polynomially equivalent to the question, "Given n and k, ... conceivably be NP-complete, and so loosely people say that factoring ... traveling salesman tour is NP-complete. ... >don't work by magic, so somewhere within the AKS algorithm, at least ...
    (comp.theory)
  • Re: Factoring integers on a classical computer
    ... Factoring is polynomially equivalent to the question, "Given n and k, ... conceivably be NP-complete, and so loosely people say that factoring ... traveling salesman tour is NP-complete. ... >don't work by magic, so somewhere within the AKS algorithm, at least ...
    (sci.math)