Computational problem

In theoretical computer science, a problem is something that asks for a way to find a solution using a special set of steps called an algorithm. One common example is the problem of factoring. This means taking a positive whole number and finding a smaller prime number that divides it exactly. There are many known ways, or integer factorization algorithms, to solve this kind of problem.

A computational problem can be thought of as a group of different cases, along with possible answers for each case. The big question is whether there is an algorithm that can take each case and give the right answer. For the factoring problem, the cases are the numbers we want to break down, and the answers are the prime numbers that are factors of them. However, not all problems have solutions. An example of this is the Halting problem, which asks whether a computer program will ever stop running, and this problem has no general solution.

People who study computers also care about how fast or slow an algorithm can be. This area of study is called computational complexity theory. It looks at how much time, memory, or other resources are needed to solve a problem. Some problems are easy to solve, while others are very hard or even impossible to solve completely. Problems that can be solved are grouped into categories called complexity classes. These classes describe the resources needed to solve them using different kinds of computers, like regular computers or special quantum computers.

Both the cases and the answers in these problems are written using strings of 0s and 1s, called binary strings. For example, normal whole numbers are often turned into these binary strings. This is important because the difficulty of solving a problem is measured by how long these strings are.

Types

Decision problem

A decision problem is a type of problem where the answer can only be yes or no. For example, one decision problem is primality testing:

"Given a positive integer n, determine if n is prime."

Search problem

In a search problem, the answers can be many different things. For example, factoring is a search problem where you are given a number and need to find its prime factors.

Counting problem

A counting problem asks how many answers there are to a search problem. For example, one counting problem linked to factoring is:

"Given a positive integer n, count how many prime factors n has."

Optimization problem

An optimization problem asks for the best possible answer from all the answers to a search problem. An example is the maximum independent set problem:

"Given a group of points connected by lines, find the largest group of points where no two points are connected by a line."

Function problem

In a function problem you need to find one specific answer for each input, and the answer is more detailed than just yes or no. A famous example is the traveling salesman problem:

"Given a list of cities and the distances between each pair, find the shortest route that visits each city exactly once and returns to the starting city."

This is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

Promise problem

Main article: Promise problem

In computer science, we usually think that any string of 0s and 1s can be used as a problem to solve. But sometimes, only certain strings are valid examples of the problem. These special types of problems are called promise problems.

For example, imagine you are given a graph and need to decide if every group of points that are not connected (called an independent set) has at most 5 points, or if the graph has an independent set with at least 10 points. Only graphs that meet one of these two conditions are considered valid for this problem.

Promise problems are important in areas like studying how hard it is to find close-to-best answers and checking properties of objects through questions and answers.