next up previous contents
Next: Reducibility Up: Problems Previous: Problems

A problem is a yes-no question

A problem is essentially a question for which we want an answer yes-no answer [Hopcroft p. 177], which can be thought of as a boolean function, the domain of which are the instances of the problem.