It's exponential, you can solve it for N=100, but not for N=1,000,000. You can't say "it just takes a lot of time" if that time is > age of the universe.
Actually, you can. There's a huge gulf between things that we know we could compute given enough time, even if that time is impossible to actually be given, and things we know can never be computed given infinite computing power.
Something like the perfect security of either hiding or binding in a commitment protocol can never be broken given computers of infinite capacity and speed because it's mathematically impossible. That is opposed to computational security, which only states that the property can't be broken within any usable time frame. This is often in the order of hundreds of millions of years in practical cryptographic systems. The point is, it can be technically be done.
Breaking RSA can factored just by brute forcing. It might take a lot of time, but actually doing it is not hard for sufficiently small keys. We just increase the key size until it takes a long time.
> You can't say "it just takes a lot of time" if that time is > age of the universe.
1. The difference matters a WHOLE LOT when you're studying computability. If the question you're trying to answer is "Can this be computed exactly?", then the distinction is paramount.
2. Your argument here is functionally equivalent to stating that there exists a largest number since it's trivial to construct a number which would require more digits (in any base you'd like) than subatomic particles in the entire universe to represent in its fully-expanded form… so let's pick this one as the largest and stop worrying about all of that infinity hub-bub!
There is a fundamental difference between "We don't know how to solve this practically since the best solution we have would take too much time." and "It is a problem without solution. It can not be solved at all not matter how you approach it, or even how an imaginary alien specie with technology beyond our understanding would approach it".
Also, the equivalence between the different models of computation for Turing completeness (turing machine, lambda calculus, ...) isn't about complexity classes of the problems, only wether or not the model allow to solve the same set of problems. For example searching in a sorted array is O(log n) on a Von Neumann machine but O(n) on a Turing machine.
