Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Computational problem
Summary
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
"Given a positive integer n, find a nontrivial prime factor of n."
is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n.
Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources (computational complexity) solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various abstract machines. For example, the complexity classes
P, problems that consume polynomial time for deterministic classical machines
BPP, problems that consume polynomial time for probabilistic classical machines (e.g. computers with random number generators)
BQP, problems that consume polynomial time for probabilistic quantum machines.
Both instances and solutions are represented by binary strings, namely elements of {0, 1}*. For example, natural numbers are usually represented as binary strings using binary encoding. This is important since the complexity is expressed as a function of the length of the input representation.
A decision problem is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is primality testing:
"Given a positive integer n, determine if n is prime."
A decision problem is typically represented as the set of all instances for which the answer is yes. For example, primality testing can be represented as the infinite set
L = {2, 3, 5, 7, 11, .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.