Re: Proof factoring solution is closed form

From: Mark Nudelman (markn_at_greenwoodsoftware.com)
Date: 02/09/05 

Date: Wed, 9 Feb 2005 09:46:27 -0800

Larry Lard wrote:
> jstevh@msn.com wrote:
>> Rick Decker wrote:
>>> jstevh@msn.com wrote:
> [snip]
>>>> And that's a polynomial time problem, as the equation defining how
>>>> many combinations of those factors there are is a polynomial one.
>>>>
>>> That's not what we mean by a poly-time solution. In fact, one might
>>> have to search for factors in a space that could be about as large
>>> as M itself. If you're going to get a poly-time solution, you'll at
>>> least have to cut down the search to O((log M)^k), for some fixed k.
>>>
>>
>> Why?
>>
>> You aren't giving any information here, but just assertions without
>> explanation.
>
> No, he's giving you *definitions*. He's pointing out that the meaning
> you've ascribed to 'polynomial time' differs from the definition used
> by EVERYONE ELSE IN THE WORLD. You have in the past claimed to be a
> professional programmer; the fact that you appear not to know what
> 'polynomial time' means is... well, I was going to say surprising, but
> really, demonstrations of your ignorance no longer surprise.

James, if you don't know what "polynomial time algorithm" means in this
context, you shouldn't claim your algorithm is polynomial time, or you just
end up sounding ignorant. To be a polynomial time factoring algorithm, the
number of operations required must be a polynomial IN THE NUMBER OF DIGITS
OF M, not in M itself. Or, as Rick stated, the number of operations must be
O((log M)^k). (If you don't know what the Big-Oh notation means, you should
read about that too.) 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.

--Mark

Relevant Pages

  • 6P=NP: Proof: Nondeterministic Algorithm
    ... each time the algorithm is run the resulting guess may differ. ... be done in Oor polynomial time. ... verifies x if there exists a certificate y such ... Algorithm A verifies language L if for any string x Î ...
    (sci.math)
  • Re: Aspiring highest-order programmer
    ... > that today's programmers repeat the mistakes of the past because their ... not the algorithm choosen to solve it. ... it means that there is no known polynomial time algorithm to ... algorithm to solve any NP-complete problem, ...
    (comp.programming)
  • Re: JSH: Nearly done
    ... my response to your "polynomial time" below.) ... algorithms really are, so I'll tell you: For a factoring algorithm to ... it doesn't hurt to use recursion in a "proof of concept" ...
    (sci.math)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... where M is a Turing machine and p is a polynomial ... can be done in polynomial time. ... How do we verify that the algorithm we've found solves SAT? ... Consider, for a fixed integer k, the decision problem ALGSAT-k. ...
    (comp.theory)
  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)