Robert J. Hansen
rjh at sixdemonbag.org
Fri Nov 2 22:01:31 CET 2007
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
More information about the Gnupg-users