(Almost) every algorithm runs in exponential time, or merely in 'pseudo-polynomial' time.
Given a list of integers, does it contain the number 2?
O(N), where N is the size of input, right?
Wrong. Express N as 2^b, and it's O(2^b) -- exponential runtime.
So every problem (basically) is as hard as the allegedly 'extremely difficult' factorization problem and subset sum problem.
Why do computer scientists make believe problems like the factorization problem and subset sum problem are any harder for a computer to solve than one of the first algorithms you write in your intro to cs class?