Definition of decision problem in English:

decision problem


  • The problem of finding a way to decide whether a formula or class of formulas is true or provable within a given system of axioms.

    • ‘In a lecture given at Harvard during 1939-40 Tarski said: -… the solution of the decision problem in its most general form is negative.… [Surely] many mathematicians experienced a profound feeling of relief when they heard of this result.’
    • ‘Consequently, what a we-intention does, subsequent to its formation, is reduce the number of degrees of freedom in, for example, a two-by-two decision problem, from two degrees to one.’
    • ‘He worked on mathematical logic solving certain cases of the decision problem for the first order predicate calculus, simplified results of Bernays, and worked on ideas of Post, Gödel and Church.’
    • ‘In normal times, experienced professionals enjoy a stable and relatively small gap between their competence to understand the markets and the difficulty of the decision problem facing them.’
    • ‘This is a representation of ‘all logical and physical relations between variables representing the decision problem being examined.’’


1930s: translation of German Entscheidungsproblem.