What is a decision problem?

Asked

Viewed 1,021 times

7

I started reading about computer theory and came across the "decision problems".

What are these problems?

I don’t want any highly elaborate scientific article to answer the question, just a quick overview of what this is and how it can be represented.

computer-science computer-theory

2 answers

7


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

EDITED Less succinct answer:

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

The input is an arbitrary graph. The problem consists in deciding 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 an accurate definition of this language, it is necessary to decide how graphs are encoded as binary strings. Source

  • Can you be a little less succinct? For example, any and all boolean expressions, where the possible results are true and false, are classified as a decision problem?

  • It means you can take on the states at the same time 0 and 1?

  • How I answered 0 OR 1, not 0 AND 1.

  • @Cat, that’s a quantum thing. Quantum decision problems return a qubit, but the qubit only remains in that state until it is evaluated by an external system; type, quantum machines return qubits only to other quantum machines. By the way, a qubit is the overlap between true and false, which means that something can be 73% true is 27% false, not just half and half

6

A Programmer is right in his answer.

I got curious and went for 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 answer. For example, the problem: "data 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".

There are actually many implications for those who study mathematics scientifically, or for those who do research on the history of computing. But for most of us it turns out to be just a curiosity.

That does not mean that this is not of great importance. Alan Turing developed all his work on computing machines to solve problems such as the decision problem. If these problems hadn’t been proposed, we wouldn’t have all the technology we have today.

Browser other questions tagged computer-science computer-theory

You are not signed in. Login or sign up in order to post.