Decision problem

Also known as: Yes/no problem

A decision problem is a yes/no question on a finite encoding of the input: “does this graph have a Hamiltonian cycle?” not “find one.”

Complexity classes like P and NP are defined on decision problems. Optimization (“find the shortest tour”) is often cast as a family of decisions (“is there a tour of length $\leq k$?”) so membership and reductions apply cleanly.

NP-complete status is about decision versions. The search or optimization sibling may be NP-hard without itself being a decision problem in NP.

← Back to CS Glossary