Re: Factoring integers on a classical computer

cafeinst_at_msn.com
Date: 03/16/05 

Date: 16 Mar 2005 09:21:15 -0800

t...@lsa.umich.edu wrote:
> In article <1110987192.055030.165180@l41g2000cwc.googlegroups.com>,
> Pubkeybreaker <Robert_silverman@raytheon.com> wrote:
> >If P != NP (and everyone competent who works in this area
believes
> >that it does), then there will exist an entire hierarchy of
algorithm
> >complexity ranging from P to EXP. We *already* have algorithms
for
> >factoring that are sub-exponential time; factoring is not
exponential
> >time and thus extremely unlikely to be NPC.
>
> There are several misleading statements here.
>
> (a) Not everyone competent believes that P != NP. See William
Gasarch's
> poll at http://www.cs.umd.edu/~gasarch/papers/poll.ps
>
> (b) We already know that there exists an entire hierarchy of
algorithm
> complexity ranging from P to EXP; this doesn't depend on assuming P
!= NP.
>
> (c) Even if (say) SAT takes exponential time, factoring could be
> NP-complete. Many-to-one Karp reductions can bump things up in the
time
> hierarchy to a certain extent.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however
great, will
> never exceed four of those miles of which as many thousand separate
us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New
Sciences

I don't understand why anyone would suggest that factoring could be
NP-complete. It is not even in NP. In order for a problem to be in NP,
it must have a yes-no answer, which factoring does not. PRIMES is in
NP, because it has a yes-no answer and can be checked in poly-time. It
is also in P (which is in NP), as proven in 2002 with the AKS
algorithm.

Back to my argument: If primes is in P, then why doesn't it follow that
there is an algorithm which factors in poly-time? After all, algorithms
don't work by magic, so somewhere within the AKS algorithm, at least
one of the factors had to have been computed indirectly; otherwise, how
could we trust the algorithm? That factor might be hidden within the
structure of the algorithm, but it has to be there; otherwise, the
algorithm would work by magic.

Of course, I could be wrong. Dik Winter gave a counter-argument with
Fermat's Little Theorem as a way of proving that a number is composite.
I'm not sure if I buy Dik's argument or not.

Craig

Relevant Pages

  • Re: storing hierarchical values in db; methods
    ... In the years since I first did this, CPU and disk speeds have more than made up for the cost of constructing the hierarchy on the fly. ... I know that I said this didn't involve cursors, but this example minimally involves them, and it should be relatively easy to implement it without cursor. ... Before I get in to the nitty gritty I should at least give all of the credit for this algorithm ... hier node parent left_nbr right_nbr ...
    (perl.dbi.users)
  • Re: storing hierarchical values in db; methods
    ... made up for the cost of constructing the hierarchy on the fly. ... implement it without cursor. ... I should at least give all of the credit for this algorithm ... FROM hier h1, ...
    (perl.dbi.users)
  • Re: Dobkin-Kirkpatrick Hierarchical Representation creation problem
    ... What made you decide on the DK hierarchy? ... of Edelsbrunner's algorithm for computing an independent set of ... independent set would be more expensive ... refer to them in this context. ...
    (comp.graphics.algorithms)
  • Re: multiple inheritance of a dynamic list of classes?
    ... the choice of algorithm for Method ... local precedence ordering and monotonicity did not hold. ... As long as you forbid the diamond-shaped hierarchy, ... since all new-style classes inherit from 'object' you ...
    (comp.lang.python)
  • Re: Factoring integers on a classical computer
    ... > We already know that there exists an entire hierarchy of ... because it has a yes-no answer and can be checked in poly-time. ... don't work by magic, so somewhere within the AKS algorithm, at least ...
    (comp.theory)