Re: Factoring integers on a classical computer

From: Ajoy K Thamattoor (ajoyk_at_cs.stanford.edu)
Date: 03/18/05 

Date: Thu, 17 Mar 2005 16:50:22 -0800
To: Craig Feinstein <cafeinst@msn.com>

> Here is a related question: 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?

        The standard factoring problem, expressed as a decision problem
(aka primality testing), is in P. There is no known P algorithm to
actually find the factors. Of course, that doesn't strictly meet your
criterion (proven to require "super-polynomial" time), but it is
close enough.

Ajoy. 

-- 
www.stanford.edu/people/ajoyk

Relevant Pages