When Problems Are Inherently Hard

Everything we have studied so far is about making problems faster. But some problems resist speed. No matter how clever your algorithm is, no matter how many machines you throw at it, certain problems are fundamentally, mathematically, provably hard. Understanding which problems fall into this category is one of the most practically valuable things in computer science, because it saves you from wasting weeks trying to build something that cannot be built. The Two Sides of Every Problem Consider a jigsaw puzzle. Solving it (finding where each piece goes) is hard. It requires trying many combinations, backtracking when pieces do not fit, and potentially exploring a vast number of arrangements. But checking a completed puzzle is easy. You just verify that every piece fits with its neighbors.