Re:full of holes, it's full of holes (Score 1)

You're right about the first part - I should have said _any_ other NP problem (the classes go P

But about the 2nd part, prime factorization is definitely _not_ suspected to be exponentially complex, because it simply isn't. For instance, one non-deterministic polynomial algorithm would be to find any one factor (try all numbers up to sqrt(integer), then find factors of those factors, etc. Since it's nondeterministic, total time is n^2 (n attempts - only n because of non-determinism - to find a factor at a cost of n each time).