Alexander W. Janssen wrote: > A P-problem? Really?! Factoring primes is a polynomal problem nowadays? > Are you SURE about that?
People who do not know what P stands for should not attempt to whap other people around with it. P is shorthand for deterministic polynomial time. NP is nondeterministic polynomial time. Factoring is known to be in NP. Therefore, it is perfectly fair to say that it's a polynomial problem, as long as Sven is not claiming that it's deterministic polynomial, which he isn't. Nondeterministic polynomial time means it can be solved in polynomial time by a nondeterministic Turing Machine--a machine that is capable of making phenomenally lucky guesses. Deterministic polynomial time means it can be solved in polynomial time by a Turing Machine that cannot make phenomenally lucky guesses. ... Incidentally, I'm assuming you meant 'factoring composites'. Factoring prime numbers is most definitely in P. It's also in NC and Context-Free, but probably not Regular; you need a pushdown automata to parse the number as you read it, which means a context-free language is required. _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
