Well, usually we measure the difficulty of a problem by the run-time complexity of a solution to the problem. If the approach is deterministic, we'd usually care for the complexity of the best solution for the worst-case kind of problem; but it could as well be an expected run-time for a probabilistic approach.
Interestingly, you don't always actually have to _have_ an actual solution - it can be possible to determine run-time bounds (that tell you how hard your problem is at least) just on theoretical grounds. This could be, e.g., by comparing it in complexity to another problem that has already been studied and whose complexity is thus known.
Interestingly, you don't always actually have to _have_ an actual solution - it can be possible to determine run-time bounds (that tell you how hard your problem is at least) just on theoretical grounds. This could be, e.g., by comparing it in complexity to another problem that has already been studied and whose complexity is thus known.