Decision problem facts for kids

A decision problem is a special kind of question in mathematics and computer science. It's a problem that can always be answered with a simple "yes" or "no." Think of it like a true or false question, but for a computer or a math problem.

For example, imagine you have a number. A decision problem could be: "Is this number a prime number?" The answer is either "yes" (it is prime) or "no" (it is not prime). Another example is: "Do these two numbers divide each other perfectly?" Again, the answer is just "yes" or "no."

What is a Decision Problem?

A decision problem asks a question that has only two possible answers: "yes" or "no." It's like a switch that is either on or off. These problems are very important in how computers solve tasks. Computers often break down big problems into many smaller yes/no questions.

Simple Examples of Decision Problems

Let's look at some easy examples to understand this better.

Is a Number Even?

Imagine you are given a number, like 10 or 7. The decision problem is: "Is this number an even number?"

• If the number is 10, the answer is "yes."
• If the number is 7, the answer is "no."

This is a clear yes/no question.

Is a Word in a Dictionary?

Another example could be: "Is the word 'apple' found in this dictionary?"

• If you find 'apple', the answer is "yes."
• If you don't find it, the answer is "no."

This also fits the definition of a decision problem.

How Do We Solve Them?

To solve a decision problem, we need a set of instructions. This set of instructions is called an algorithm. An algorithm is like a recipe that tells you step-by-step how to get the "yes" or "no" answer. When an algorithm solves a decision problem, it's called a decision procedure.

Algorithms in Action

Let's go back to our example: "Do these two numbers, X and Y, divide each other perfectly?"

The Division Algorithm

To solve this, you could use a simple division algorithm:

• Step 1: Divide number X by number Y.
• Step 2: Check the remainder.
• Step 3: If the remainder is zero, the answer is "yes."
• Step 4: If the remainder is not zero, the answer is "no."

This step-by-step process is a decision procedure. It always gives you a "yes" or "no" answer.

Decidable and Undecidable Problems

Not all problems can be solved by an algorithm that always gives a "yes" or "no" answer in a reasonable amount of time.

What is a Decidable Problem?

A decision problem is called decidable if there is an algorithm that can always find the correct "yes" or "no" answer for any input. Most problems you solve in math class are decidable. For example, checking if a number is prime is a decidable problem. We have algorithms that can do this.

What is an Undecidable Problem?

An undecidable problem is a decision problem for which no algorithm can ever be created to always give the correct "yes" or "no" answer for every possible input. This might sound strange, but some very important problems in mathematics and computer science are known to be undecidable.

One famous example is the "Halting Problem." This problem asks: "Will a given computer program ever stop running, or will it run forever?" It has been proven that no single algorithm can always correctly answer this question for every possible program.

Why Are Decision Problems Important?

Decision problems are fundamental to how computers work and how we understand what computers can and cannot do. They help us define the limits of computation. By turning complex questions into simple yes/no choices, we can build powerful computer programs and understand the basic rules of logic and problem-solving. They are a core part of computability theory, which studies what can be computed.