Computational problem

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, a computational problem is one that asks for a solution in terms of an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a>. For example, the problem of factoring

"Given a positive integer n, find a nontrivial prime factor of n."
is a computational problem that has a solution, as there are many known <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> algorithms. A computational problem can be viewed as a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of instances or cases together with a, possibly empty, set of solutions for every instance/case. The question then is, whether there exists an algorithm that maps instances to solutions. For example, in the <a href="/facts/Factoring_problem/EjMCTz2t">factoring problem</a>, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n. An example of a computational problem without a solution is the <a href="/facts/Halting_problem/Xz1bac40">Halting problem</a>. Computational problems are one of the main objects of study in theoretical computer science. 
One is often interested not only in mere existence of an algorithm, but also how efficient the algorithm can be. The field of <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> addresses such questions by determining the amount of resources (<a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a>) solving a given problem will require, and explain why some problems are <a href="/facts/Computational_complexity_theory/etHuVF3U">intractable</a> or <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a>. Solvable computational problems belong to <a href="/facts/Complexity_class/IIKrcTbP">complexity classes</a> that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various <a href="/facts/Abstract_machine/zuC4RKLn">abstract machines</a>. For example, the complexity classes

<ul><li><a href="/facts/P_(complexity)/2TYvck4k">P</a>, problems that consume polynomial time for deterministic classical machines</li>
<li><a href="/facts/BPP_(complexity)/6woy25bz">BPP</a>, problems that consume polynomial time for probabilistic classical machines (e.g. computers with random number generators)</li>
<li><a href="/facts/BQP/whjD9eyf">BQP</a>, problems that consume polynomial time for probabilistic quantum machines.</li></ul>
Both instances and solutions are represented by binary <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a>, namely elements of {0, 1}*. For example, <a href="/facts/Natural_numbers/u65og8JE">natural numbers</a> are usually represented as binary strings using <a href="/facts/Binary_number/a6JDSRPs">binary encoding</a>. This is important since the complexity is expressed as a function of the length of the input representation.

Computational problem open-in-new

Computational problem