I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the difference between these two. Do you all have an example(s) that can help me to understand?
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.