Computational problem

In theoretical computer science, a problem is something we try to solve by following steps called an algorithm. One common example is factoring. This means taking a whole number and finding smaller prime numbers that divide it exactly. There are many ways, or integer factorization algorithms, to solve this.

A computational problem has many different cases, each with possible answers. 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. But not all problems have solutions. An example is the Halting problem, which asks if a computer program will ever stop running. This problem has no general solution.

People who study computers also care about how fast 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. 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.

Both the cases and the answers in these problems are written using strings of 0s and 1s, called binary strings. For example, 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 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.