- we are given an instance $I$ (input data specifying the problem) - we are asked to find solution $S$ (object that meets specification) - a problem is a "search problem" if there's an algorithmic way to verify the answer - search problems are specified by an algorithm $C$ (c for check) - which takes 2 inputs: - an instance $I$ - a proposed solution $S$ - runs in $O(|I|)$ - $S$ is a solution to $I$ $\iff$ $C(I, S) == true$ https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf https://cs.stackexchange.com/questions/105760/what-is-a-search-problem