How are "Problem Complexity" and "Solution Complexity" different?
Problem complexity is the best we can achieve for a given problem (sometimes under given restrictions). We usually talk about problem complexity when dealing with lower-bounds and it means there is probably no algorithm with lower time/place complexity than the proved ones.

Algorithm complexity is on the other hand the resources needed for a specific algorithm to run. When some algorithm solves a given problem in time $t$, we know that this problem has at most time complexity $t$ and hence, the complexity of an algorithm is an upper-bound for the complexity of the problem it solves.