Problem of decision

One speaks about problem of decision in varied contexts. This article is intended to describe this term in data processing, or mathematics.

In Algorithmic, a problem of decision is a mathematically definite question carrying about parameters given in form easy to handle by means of computer, and requiring an answer by yes or not.

Thus, knowledge if, being given the distances between the towns of a chart and a distance D , there exists a way passing by all the cities and from length lower than D , is a problem of decision.

A problem of decision can be Indécidable if there does not exist any computer program which makes it possible to solve it (without restriction of memory or time), which one formalizes by impossibility of answering the problem using a Machine of Turing.

Certain problems of decision décidables are however regarded as nondécidables in practice for reasons of too great complexity of calculations. The Théorie of complexity gives a hierarchy of formal complexities. In particular, a Np-complete problem will not have an exact solution in practice, except on particular cases or authorities of sufficiently small size.

See too

Problem of the decision

Random links: