The lesson states that “The lesson touches on computationally hard problems”
When it says hard, what is the specific level of hardness? Would it be considered NP-Hard?
Thanks,
Bill
WARNING - NERD HATS ON:
Optimal Text-Compression does happen to be NP-Hard. It is in NP-Hard because, in strictly layman’s terms, given some algorithm that compresses a piece of text (say using the LZW technique of pattern substitution we use in the course) there is no way to verify that you have achieved optimal compression without trying every single permutation of pattern substitution by brute force. There are heuristics that can make pretty-good compression, but you cannot know or verify that it is optimal. Just for completeness, there is a distinction between a problem like this and a “hard” decision problem, one that might be hard to compute but results in a yes/no answer that is easily verifiable (example: can this map be colored using only 4 colors? To compute this solution I might have to try every single permutation of assigning colors to regions, but if it results in a 4-coloring, it is very quick to verify that).
NERD HAT OFF:
For the record, for CSP, students understanding what NP or NP-hard is, is actually explicitly excluded from the CSP framework. For CSP I would say students only need a kind of gut-level sense of what makes something computationally hard (unfortunately the “hard” here is colloquial and doesn’t really relate to “NP-Hard”) is that it will take an “unreasonable amount of time to compute” – it can usually be expressed as “some problem for which the only known way to compute the answer is to make the computer run for a very long time trying all the possibilities or permutations”.
The word “hard” is tricky here because of its colloquial usage. As a bit of I mind bender it might be worth noting that a lot of problems that are “computationally hard” are actually trivial to solve in terms of designing an algorithm. That is, we know how to solve the problem computationally, it’s just that the Earth will collide with the sun before the computer finishes, which is a good working definition for “unreasonable amount of time.” 
Yet for students, what makes a problem or algorithm “hard” might be how hard it is to understand how or why it works. Don’t confuse these two:).
Hope this helps.
-Baker
2 Likes