[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: dpkg-sig support wanted?

On Mon, Nov 28, 2005 at 03:32:21PM +1000, Anthony Towns wrote:

> Knapsack cryptograph's "provably" secure (in that a general solution
> is NP),

You mean NP-_complete_. (Sorting is also NP, but not NP-complete. NP
is "can be done in polynomial time by a non-deterministic Turing
machine, so anything polynomial by a normal machine is also
NP. "Foo is NP-complete" is "any NP problem can be polynomially
reduced to foo", or in other words, if there is a normal machine that
does foo in polynomial time, all NP problems can be done in polynomial


Reply to: