Re: Factoring integers on a classical computer

cafeinst_at_msn.com
Date: 03/15/05 

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

Amar wrote:
> > > "Note: It is known that there are methods out there which are
more
> > > practical than brute force, but these methods don't always work
so
> > > well and when they do not work so well, they run slower than the
> > brute
> > > force method. "
> > >
> > > Is totally false.
> >
> > Why is it false? There are no practical methods out there that beat
> > brute force for the majority of cases but sometimes work badly?
>
> It is false because your statement seemed to imply that FACTORING is
in
> EXPTIME (or any class outside NP but within EXPTIME).
>
> [EXPTIME is a class of problems which will take exponential running
> time in the worst case.
> An example is a problem "which of the permutations of a set of
numbers
> satisfies propery X", where X
> can be *any* property and so can be given at runtime of the
algorithm.
> If X is known apriori, for example for sorting: "are they in strict
> nondecreasing order?", we could solve the problem in polhynomial
time,
> as we know any of the sorting methods work.]
>
> Now, your argument seems to say that "for factoring, brute force is
the
> same as any other algorithm over the range of all possible
algorithms".
> Computer science has long concentrated on looking at problems that
are
> in a smaller set, namely NP: which can be verified in polynomial
time.
> So, it could be true that factoring is proved not to be in P. But, we
> will never be worried about the fact when it "falls out" of NP, into
> EXPTIME. It will not, because, it was never defined to be that way.
>
> It will (less probably, as other posters seemed to imply) fall into
the
> NP-Complete set, the hardest problems in the NP (running time is as
> *slow* as brute-force). Even then, algorithms to solve factoring
would
> run *as slow* as brute-force, not any *slower*. That is because, if
> they run any *slower* than brute force over the bad cases of input,
> factoring would "fall out" of the category NP.
>
> Of course, we need not discuss the case when it falls out into the
> category, as then brute force would be beaten black and blue:)
>
> Amar

Factoring is not NP-complete. It's not even in NP, because it is not a
decision problem.

Craig

Relevant Pages

  • Re: Factoring integers on a classical computer
    ... There are no practical methods out there that beat ... > It is false because your statement seemed to imply that FACTORING is ... > EXPTIME. ... > Now, your argument seems to say that "for factoring, brute force is ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... There are no practical methods out there that beat ... > <brute force for the majority of cases but sometimes work badly? ... "Intro to Algorithms" is not always successful, ...
    (comp.theory)
  • Re: Factoring integers on a classical computer
    ... There are no practical methods out there that beat ... > <brute force for the majority of cases but sometimes work badly? ... "Intro to Algorithms" is not always successful, ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... >> practical than brute force, but these methods don't always work so ... Now, your argument seems to say that "for factoring, brute force is the ... same as any other algorithm over the range of all possible algorithms". ... not any *slower*. ...
    (comp.theory)
  • Re: Factoring integers on a classical computer
    ... >> practical than brute force, but these methods don't always work so ... Now, your argument seems to say that "for factoring, brute force is the ... same as any other algorithm over the range of all possible algorithms". ... not any *slower*. ...
    (sci.math)