In the Partition problem, there are $n$ positive integers, and the problem is to decide whether they can be partitioned into two subsets with an equal sum. If all integers are "small" (at most some polynomial in $n$), then the problem can be solved in time polynomial in $n$ using dynamic programming. But if the integers are large (exponential in $n$), then the problem is NP-hard.
What if we constrain the possible inputs to integers that are doubly-exponential in $n$, that is, we only care about instances in which the integers are at least $2^{2^n}$. In this case, the binary encoding length of the input is at least $2^n$. Therefore, the brute-force algorithm that checks all possible partitions is polynomial in the input size. Is it true to say, therefore, that the Partition problem when all integers are "very large" is in P? So the problem is NP-hard only in the middle range, where the inputs are large but not too large?
