Re: Proof factoring solution is closed form

From: Timothy Little (tim-via-n.i.net_at_little-possums.net)
Date: 02/09/05 

Date: 9 Feb 2005 22:23:48 GMT

Mark Nudelman wrote:
> This is not just an arbitrary definition -- a poly-time algorithm
> MIGHT be able to factor a large integer in a reasonable amount of
> time (depending on the degree of the polynomial), but an
> non-poly-time algorithm (e.g. exponential time) simply will not.

In theory, for large enough N, sure. In practice, I'd much rather
have a 1.001^N exponential factoring algorithm than N^5 polynomial.

There's also the question of the domain over which the
characterization is defined. Worst-case? Average-case? Only numbers
with just two prime factors?

- Tim