I’m just computational complexity theory enthusiast, but my opinion is that P vs NP centered explanation of computational complexity is confusing. Explanation of NP should happen in the very end of the course.
There is nothing difficult in proving that computationally hard functions exist: time hierarchy theorem implies that, say, P is not equal EXPTIME. Therefore, EXPTIME is “computationally hard”. What is difficult is to prove that very specific class of problems which have zero-error polynomial-time verification algorithms is “computationally hard”.
I’m just computational complexity theory enthusiast, but my opinion is that P vs NP centered explanation of computational complexity is confusing. Explanation of NP should happen in the very end of the course.
There is nothing difficult in proving that computationally hard functions exist: time hierarchy theorem implies that, say, P is not equal EXPTIME. Therefore, EXPTIME is “computationally hard”. What is difficult is to prove that very specific class of problems which have zero-error polynomial-time verification algorithms is “computationally hard”.