Re: Factoring integers on a classical computer

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

  • Next message: Craig Feinstein: "Re: Factoring integers on a classical computer" 
    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).

  • Next message: Craig Feinstein: "Re: Factoring integers on a classical computer"

    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 ...
      (sci.math)
    • 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: 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)
    • Re: The factoring problem
      ... > in the class NP-complete would be accepted by many as such ... > know there has never been an accepted proof that factoring ... > like an NP-complete problem. ...
      (sci.crypt)