In mathematics, the (, German for 'decision problem') is a challenge posed by David Hilbert in 1928. The asks for an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

Eine Entscheidung ist eine Wahl zwischen Alternativen oder zwischen mehreren unterschiedlichen Varianten anhand bestimmter Präferenzen von einem oder mehreren Entscheidungsträgern. Sie kann spontan bzw. emotional, zufällig oder rational erfolgen. Eine rational begründete Entscheidung richtet sich nach bereits vorgängig abgesteckten Zielen oder vorhandenen Wertmaßstäben. Die Eigenschaft, ohne Verzug zu entscheiden und dabei zu bleiben, wird als Entschiedenheit bezeichnet (vgl. Führung). Die Statistik und Ökonomie befasst sich in der Entscheidungstheorie mit der Frage nach der optimalen Entscheidung. Das Wort soll von ent-scheiden stammen, also z. B. das Schwert aus dessen Scheide ziehen, da man sich dann eben zwischen kämpfen bzw. nicht kämpfen entschieden hat. Die Entscheidung wird auch, oftmals im Sinne eines Ergebnis, als der Entscheid bezeichnet.

Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht. Wenn es ein solches Entscheidungsverfahren nicht gibt, dann nennt man die Eigenschaft unentscheidbar. Als Entscheidungsproblem bezeichnet man die Frage, ob und wie für eine gegebene Eigenschaft ein Entscheidungsverfahren formuliert werden kann.