Decision problem

A decision problem asks whether an input satisfies a specified condition, with answers restricted to yes or no. Its solvability concerns whether an effective procedure can produce the correct answer for every input.

Yes–no question: A question whose possible answers are limited to yes and no. A decision problem formalizes a yes–no question over a specified range of inputs.
Decidable language: A formal language for which an algorithm always halts and correctly decides membership. A decision problem is solvable exactly when its yes-instances form a decidable language.
Optimization problem: A problem that seeks the best feasible solution according to an objective function. Unlike a decision problem, it asks for an optimal solution rather than a yes-or-no answer.
Satisfiability problem: The problem of determining whether a logical formula has a satisfying assignment. It is a foundational decision problem connecting logic with computational complexity.
Formal language: A set of finite strings over a specified alphabet. The yes-instances of a decision problem can be represented as a formal language.
Recognizer (computability): A program that accepts members of a language but may run forever on nonmembers. Recognition can establish yes answers without guaranteeing a decision for every input.
Search problem: A problem that asks for a witness satisfying specified constraints, when one exists. A decision answer reports existence; a search answer must produce a witness.
Primality test: An algorithmic procedure that determines whether an integer is prime. Primality is a concrete decision problem with an efficient algorithm.
Algorithm: A finite, precise procedure for computing an output from an input. An algorithm is the proposed effective procedure for deciding every instance.
Halting problem: The problem of deciding whether an arbitrary program halts on a given input. It is a canonical decision problem proved impossible to solve in full generality.

Linked from 20 pages