**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

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)

Related publications (157)

Related people (33)

Related units (3)

Related concepts (19)

Related lectures (37)

Ontological neighbourhood

CIVIL-557: Decision-aid methodologies in transportation

The course proposes an introduction to operations research, and mathematical modelling for decision support in transportation systems.

MGT-487: Complex problem solving in organizations

As a professional you will face unfamiliar challenges that will require you to think strategically. This course develops your strategic thinking by giving you a step-by-step process and actionable too

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

, , , , , , , , ,

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"..

Covers the Cincent Model of Deutsch for Quantum Computation, focusing on input representation, Hilbert space, and unitary evolution.

Explores RSA cryptography computational problems, finite fields construction, and computational challenges in RSA cryptography.

Explores the challenges of fixing a tricky computer virus amidst personal struggles and upcoming events.

This paper develops a fast algorithm for computing the equilibrium assignment with the perturbed utility route choice (PURC) model. Without compromise, this allows the significant advantages of the PURC model to be used in large-scale applications. We form ...

Richard Lee Davis, Engin Walter Bumbacher, Jérôme Guillaume Brender

How to measure students' Computational Problem-Solving (CPS) competencies is an ongoing research topic. Prevalent approaches vary by measurement tools (e.g., interactive programming, multiple-choice tests, or programming-independent tests) and task types ( ...

Deep learning has revolutionized the field of computer vision, a success largely attributable to the growing size of models, datasets, and computational power.Simultaneously, a critical pain point arises as several computer vision applications are deployed ...