Re: Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/17/05 

Date: 17 Mar 2005 12:18:36 -0800

Pubkeybreaker wrote:
> "Can anyone give an example of a problem in
> which determining whether a solution exists is easy (can be done in
> poly-time), but where finding the solution has been proven to require
> super-polynomial time? "
>
>
> May I suggest you think about what having a proof of *any* algorithm
> requiring
> more than polynomial time would have upon the P = NP question.......

Interestingly, this question does relate to the p vs. np problem in the
following way. Pick your favorite np-complete problem; mine is
subset-sum. If one had an algorithm (let's call it algorithm A) which
determines whether there is a solution to subset-sum in poly-time, one
could easily determine a solution to subset-sum in poly-time in the
following way:

Split the subset-sum problem into two subproblems. If the subset is
{s1,..,sn} and the target is t, then the subset-sum problem is
equivalent to determining whether there is a solution to the two
subproblems {s1,..,s(n-1)} with target t and {s1,..,s(n-1)} with target
t-sn and taking the OR operator of the results.

Apply A to each of the two subproblems. Pick any of the subproblems in
which A outputs that there is a solution to subset-sum and then split
that subproblem into two subproblems. Then apply A to each of these and
continue the process until you reach a subset of size 1, where it is
easy to find a solution in poly-time with respect to n.

However, I can't see how this reasoning can apply to the integer
factoring problem, even though I would like to believe that there is
some way to do such. So if one could find a problem in which
determining whether there is a solution is easy but determining the
solution is difficult, that problem would not be np-complete.

Craig