What is a decision problem?

7

I started to read about computer theory and came across "decision problems".

What are these problems?

I do not want any highly elaborate scientific articles to answer the question, just a quick overview of what this is and how it can be represented.

    
asked by anonymous 28.07.2017 / 14:34

2 answers

7

Being brief and succinct a decision problem is a special type of computational problem which answer is yes or no or alternatively 1 or 0.

EDITED Less succinct answer:

Anything that you can represent as a function that takes a parameter and has a Boolean example:

The input is an arbitrary graph. The problem is whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs-obviously, to get a precise definition of this language, we must decide how graphs are encoded as binary strings. Source

    
28.07.2017 / 14:40
6

A Scheduler is right in his response.

I became curious and went after more material. I found this on Wikipedia :

  In computability theory and computational complexity theory a decision problem is a question about a formal system with a yes-or-no response. For example, the problem: "Given two numbers x and y, y is divisible by x?" is a decision problem. (...)

So for all practical purposes, we can interpret this as "anything you can represent with a function / method that considers a condition and returns Boolean."

In fact there are many implications on this for anyone studying mathematics scientifically, or for anyone doing research on the history of computing. But for most of us it turns out to be just a curiosity.

Q.: That is not to say that this is not of great importance. Alan Turing has developed all his work on computing machines to solve problems like the decision problem. If these problems had not been proposed, we would not have all the technology we have today.

    
28.07.2017 / 14:50