Understand tractable and intractable problems, the classes P and NP, the idea of computable and non-computable problems, and the use of heuristics for intractable problems.

A tractable problem can be solved by an algorithm that runs in polynomial time, such as $O(n)$ or $O(n^2)$, so it remains practical even for large inputs. An intractable problem has a solution in theory but no known polynomial-time algorithm; the best-known algorithms grow far faster (for example $O(2^n)$ or $O(n!)$), so the running time becomes impossibly long as the input grows.

The travelling salesperson problem (finding the shortest route visiting every city) is intractable, so for many cities an exact solution cannot be found in reasonable time. A heuristic is used instead: a rule-of-thumb method (such as always going to the nearest unvisited city) that finds a good-enough, near-optimal route quickly, accepting that it may not be the absolute best.

Markers reward the polynomial versus no-known-polynomial distinction and explaining that a heuristic trades guaranteed optimality for a fast, good-enough answer.

An intractable problem is solvable in principle but has no known algorithm that runs in reasonable (polynomial) time, so it is impractical for large inputs. A non-computable problem has no algorithmic solution at all, regardless of how much time is available; the halting problem is the classic example. The key difference is that an intractable problem can be solved (just too slowly), whereas a non-computable one can never be solved by any algorithm.

Class P is the set of problems that can be solved in polynomial time. Class NP is the set of problems whose proposed solution can be verified in polynomial time. Every problem in P is also in NP (if you can solve it quickly you can check it quickly). Whether P equals NP, that is whether every quickly-checkable problem is also quickly solvable, is a famous open question.

Markers reward the solvable-but-slow versus no-algorithm distinction and a correct account of P (solvable in polynomial time) and NP (verifiable in polynomial time) with P being a subset of NP.