Re: unprovability of the security of computational cryptography

From: Foo Bar (foobar965_at_hotmail.com)
Date: 10/13/03 

Date: Mon, 13 Oct 2003 13:01:35 GMT

Mack <macckone@a_nospamjunk123_ol.com> writes:

<SNIP>
>
> Would not a proof that P=NP involve showing that at least one
> NP complete problem can be definitively solved in P?

It would imply that all problems in NP can be solved in polynomial
time. However, the proof does not necessarily have to provide a
polynomial time algorithm for a NP-complete problem. Think proof by
contradiction, for example.

/FB 

-- 
Foo Bar (foobar965@hotmail.com)