It's been a long time since my computer science classes. But I'll give it a shot. The general name for this topic is complexity theory, the study of how inherently difficult certain classes of problems are to solve. Perhaps a not unreasonable summary would be problems in the class "P" can be solved in deterministic polynomial time. Some of these would include problems like simple sorting of strings that your OS does whenever it displays files in a directory. "NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P. Of relevance to our discussion is that factoring is a NP problem. Much of modern cryptography relies on factoring being a "hard" problem. If it is not, things will get interesting quickly. :) Arnold Reinhold has another view here, saying P=NP is not relevant to crypto: http://world.std.com/~reinhold/p=np.txt -Declan (PS: don't use the toad.com address) On Fri, Nov 03, 2000 at 07:40:51PM +0100, Olav wrote:
Perhaps someone could explain this P vs. NP stuff to a normal not-yet-student? And, this program, what features are required to prove his theory?
Thanks in advance, Olav
On Thu, 02 Nov 2000, you wrote:
http://digitalmass.boston.com/news/daily/11/01/minesweeper.html
from the article: "Proving the conjecture false would mean that modern encryption technology, the foundation of electronic commerce, would be open to easy attack."
Isn't that a little general? Possibly jumping to some hasty conclusions about P versus NP as well?