EPFL Logo
fr|en
Login
Concept

Computational problem

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.
Related courses (13)
CIVIL-557: Decision-aid methodologies in transportation
The course has two modules, the first Operations Research (OR), and the second is statistical modeling of transportation systems. Students will be modeling applied problems and developing solution met
MGT-487: Complex problem solving in organizations
As a professional you will need to solve all sorts of complex problems, requiring you to think strategically. This course develops your strategic thinking skills by giving you a three-step process and
EE-735: Online learning in games
This course provides an overview of recent developments in online learning, game theory, and variational inequalities and their point of intersection with a focus on algorithmic development. The prima
Show more
Related concepts (19)
Promise problem
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no.
Search problem
In the mathematics of computational complexity theory, computability theory, and decision theory, a search problem is a type of computational problem represented by a binary relation. Intuitively, the problem consists in finding structure "y" in object "x". An algorithm is said to solve the problem if at least one corresponding structure exists, and then one occurrence of this structure is made output; otherwise, the algorithm stops with an appropriate output ("not found" or any message of the like).
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. A decision problem is a question which, for every input in some infinite set of inputs, answers "yes" or "no"..
Show more

Copyright © 2025 EPFL, all rights reserved

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.