Concept

Decision problem

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable. The field of computational complexity categorizes decidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of recursion theory, meanwhile, categorizes undecidable decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution. A decision problem is a yes-or-no question on an infinite set of inputs. It is traditional to define the decision problem as the set of possible inputs together with the set of inputs for which the answer is yes. These inputs can be natural numbers, but can also be values of some other kind, like binary strings or strings over some other alphabet. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined as formal languages.

Official source

https://en.wikipedia.org/wiki/Decision_problem

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 (32)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees

ME-411: Mechanics of slender structures

Analysis of the mechanical response and deformation of slender structural elements. ...

Related units (29)

Transportation and Mobility Laboratory

TRACE - Administration

Chair of Discrete Optimization

Graph Chat

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.

Official source

https://en.wikipedia.org/wiki/Decision_problem

About this result

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computational complexity theory

Related courses (32)

CS-101: Advanced information, computation, communication I

EE-556: Mathematics of data: from theory to computation

ME-411: Mechanics of slender structures

Analysis of the mechanical response and deformation of slender structural elements. ...

Related lectures (32)

Theory of Computation: Undecidable Problems

Explores the existence of functions that cannot be computed, illustrated by famous paradoxes and the concept of undecidable problems.

Introduction to MATLAB and Octave

Provides an introduction to MATLAB and Octave, focusing on basic usage and key features.

Theory of Computability: Solvability and Complexity

Explores the theory of computability, decision problems, complexity classes, and the 'P vs. NP' conundrum.

Related publications (32)

The semi-explicit nonsmooth Newmark-β time integrator for robust unilateral contact in dynamic fragmentation simulations

Numerical simulations of solids undergoing dynamic fragmentation, a problem characterized by dynamic fracture and dense contacts, require accurately capturing the transition from a solid continuum to a collection of interacting fragments. We use the finite-element method with the extrinsic cohesive zone model for fracture. For contact, conventional penalty-based methods often exhibit numerical instabilities in dynamic collision-rich settings. To address this, we adapt and validate a novel semi-explicit time

2027

On the security of two blind signatures from code equivalence problems

The Linear Code Equivalence (LCE) problem and the Matrix Code Equivalence (MCE) problem are two examples of code-based hard problems that have gained attention as candidates for use in post-quantum cryptography. They are straightforward to implement, can be viewed as group actions, and offer a good trade-off between compactness and performance in the realm of post-quantum group actions. With the community gaining confidence in the security of these problems, new variants of these problems have been introduc

International Association for Cryptologic Research2026

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior works on JRP and its generalizations have focused on the clairvoyant setting. Recently, Touitou [Tou23a] developed a non-clairvoyant framework that provided an O(√ n log n) upper bound for a wide class of generalized JRP, where n is the number of request types.

Springer Science and Business Media LLC2026

Related people (32)

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Martin Vetterli

Martin Vetterli was appointed president of EPFL by the Federal Council following a selection process conducted by the ETH Board, which unanimously nominated him. Professor Vetterli was born on 4 October 1957 in Solothurn and received his elementary and secondary education in Neuchâtel Canton. He earned a Bachelor’s degree in electrical engineering from ETH Zurich (ETHZ) in 1981, a Master’s of Science degree from Stanford University in 1982, and a PhD from EPFL in 1986. Professor Vetterli taught at Columbia University as an assistant and then associate professor. He was subsequently named full professor in the Department of Electrical Engineering and Computer Sciences at the University of California at Berkeley before returning to EPFL as a full professor at the age of 38. He has also taught at ETHZ and Stanford University. Professor Vetterli has earned numerous national and international awards for his research in electrical engineering, computer science and applied mathematics, including the National Latsis Prize in 1996. He is a fellow of both the Association for Computing Machinery and the Institute of Electrical and Electronics Engineers and a member the US National Academy of Engineering. He has published over 170 articles and three reference works. Professor Vetterli’s work on the theory of wavelets, which are used in signal processing, is considered to be of major importance by his peers, and his areas of expertise, including image and video compression and self-organized communication systems, are central to the development of new information technologies. As the founding director of the National Centre of Competence in Research on Mobile Information and Communication Systems, Professor Vetterli is a staunch advocate of transdisciplinary research. Professor Vetterli knows EPFL inside and out. An EPFL graduate himself, he began been teaching at the school in 1995, was vice president for International Affairs and then Institutional Affairs from 2004 to 2011, and served as dean of the School of Computer and Communication Sciences in 2011 and 2012. In addition to his role as president of the National Research Council of the Swiss National Science Foundation, a position he held from 2013 to 2016, he heads the EPFL’s Audiovisual Communications Laboratory (LCAV) since 1995. Professor Vetterli has supported more than 60 students in Switzerland and the United States in their doctoral work and makes a point of following their highly successful careers, whether it is in the academic or business world. He is the author of some 50 patents, some of which were the basis for start-ups coming out of his lab, such as Dartfish and Illusonic, while others were sold (e.g. Qualcomm) as successful examples of technology transfer. He actively encourages young researchers to market the results of their work.

Patrick Thiran

Patrick Thiran is a full professor in network and systems theory at the School of Computer and Communication Sciences at EPFL. He holds an electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, an M.Sc. degree in electrical engineering from the University of California at Berkeley, USA, and he received the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002, an associate professor in 2006 and a full professor in 2011. He was with Sprint Advanced Technology Labs in Burlingame, California, in 2000-01. His research interests are in communication and social networks, performance analysis and stochastic models. He is currently active in the analysis and design of wireless and PLC networks (scaling laws, medium access control), in network monitoring (network tomography, multi-layer networks), and data-driven network science. He also contributed to network calculus and to the theory of locally coupled neural networks and self-organizing maps. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99 and for the IEEE/ACM Transactions on Networking in 2006-10. He is currently on the editorial board of the IEEE Journal on Selected Areas in Communication. He is/was on the program committee of different conferences in networking, including ACM Sigcomm, Sigmetrics, IMC, CoNext and IEEE Infocom. He was TPC chair of AMC IMC 2011 and CoNext 2012. He is a Fellow of the Belgian American Educational Foundation and of the IEEE. He received the 1996 EPFL Doctoral Prize and the 2008 Crédit Suisse Teaching Award.

Giovanni De Micheli

Expertise Design technologies for integrated systems on silicon, such as synthesis, hw/sw codesign and low-power design, as well as systems on heterogeneous platforms including electrical and biological components. Scientific Director of EcoCloud Center at EPFL Directing activities towards creating sustainable computation including AI.Designing energy-savvy data centers and edge devices. More information Please read http://si2.epfl.ch/~demichel/ Giovanni De Micheli is a research scientist in electronics and

Mika Tapani Göös

Website https://theory.epfl.ch/mika/ Teaching & PhD PhD Students Valentin Imbach, Ziyi Guan, Artur Riazanov, Anastasiia Sofronova, Weiqiang Yuan Past EPFL PhD Students Maystre Gilbert Théodore Courses Computational complexity CS-524 In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation. This course advances the students knowledge of computational complexity, and develop an understanding o

Anouk Neuenschwander

Teaching & PhD Courses Business law HUM-234 This course provides legal tools for the analysis of concrete economic situations and the identification of relevant rules from a business perspective. Law and technology I HUM-410 This course presents the legal framework applicable to certain issues in technical fields, such as construction law, computer law, biotechnology, data protection, digitalisation, robotization. Law and technology II HUM-414 This course pres

Oliver Janzer

Teaching & PhD PhD Students Rik Sarkar Courses Algebraic methods in combinatorics MATH-526 In this course we study how algebraic methods can be used to solve problems in combinatorics. The main tools used are from linear algebra and from the theory of polynomials. Graph theory MATH-360 The course aims to introduce the basic concepts and results of modern Graph Theory. Awards European Prize in Combinatorics 2025 British Combinatorial Committee PhD Prize 2022 Smith-Knight

Serge Vaudenay

Serge Vaudenay entered at the Ecole Normale Supérieure in 1989 with a major in mathematics. He earned his agrégation (secondary teaching degree) in mathematics in 1992, then a PhD in Computer Science at the University of Paris 7 - Denis Diderot in 1995. He subsequently became a senior research fellow at the CNRS, prior to being granted his habilitation à diriger des recherches (a postdoctoral degree authorizing the recipient to supervise doctoral students). In 1999, he was appointed as a Professor at the EPFL, where he created the Security and Cryptography Laboratory.

Laura Grigori

Expertise Numerical linear algebra, deterministic and randomized algorithmsHigh performance computing for scientific applicationsHigh dimensional problems and tensor computationsApplications in astrophysics, molecular simulations, etcCombinatorial scientific computingMathematical Software Teaching & PhD PhD Students Israa Fakih, Zhipeng Xue, Andrea Di Antonio, Mariana Graciela Martinez Aguilar, Guifré Sánchez i Serra Courses Numerical analysis and computational mathematics MATH-456 The cou

Michael Herbst

Expertise For more information about our research, see https://matmat.org/research/. Teaching & PhD PhD Students Niklas Frederik Schmitz, Anna Paulish, Bruno Ploumhans, Benedikt Menges Courses Error control in scientific modelling MATH-500 Errors are ubiquitous in computational science as neither models nor numerical techniques are perfect. With respect to eigenvalue problems motivated from materials science and atomistic modelling we discuss, implement and apply numerical techniques for e

Related units (29)

Transportation and Mobility Laboratory

TRACE - Administration

Chair of Discrete Optimization

Related concepts (30)

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Related MOOCs (5)

Information, Computation, Communication: Introduction to computational thinking

In the first part of the course, we'll look at how algorithms can be used to solve a problem in a very concrete way, leading us on to one of the great questions of modern theoretical computer science. The second part of the course will be devoted to information and communication: we'll be looking at a number of topics, including information representation, signal processing, data compression, communication and cryptography.

Optimization: principles and algorithms - Linear optimization

What you'll learn Formulation: you will learn from simple examples how to formulate, transform and characterize an optimization problem. Constraints: you will learn how to represent the constraints of a linear optimization problem, both from a geometric and algebraic point of views. Duality: you will learn how to derive a companion problem called the "dual". Optimality conditions: you will learn sufficient and necessary conditions for an optimal solution. Simplex method: you will learn an algorithm to solve

Learning to study science and engineering

Why take this course? Joining a scientific university course such as EPFL is the start of an exciting and exhilarating journey. Nevertheless, this type of study is generally very difficult and requires a huge investment of time and energy. Even those who work between 50 and 60 hours a week can sometimes struggle to keep up with everything they have to do... You've undoubtedly heard countless pieces of advice - often contradictory - on the most effective ways to study, but which methods are really proven t

Related exercises (32)

Gauss s law for magnetism

A Gaussian surface in the shape of a right circular cylinder has a radius of 13u2006cm and a length of 80u2006cm. Through one end there is an inward magnetic flux of 25u2006μWb, where

1\,{\rm Wb\,(Weber)} = 1\,{\rm T}\cdot {\rm m}^2

. At the other end there is a uniform magnetic field of 1.6u2006mT, normal to the surface and directed outward. Calculate the net magnetic flux through the curved surface. Total flux of magnetic field through a closed surface is equal to 0 according to the Gauss’s law for magne

The crow and the fox

A few days after the events narrated in the famous fable[1], the crow and the fox meet again. Having learned from its mistakes, the crow is determined not to be fooled again by the fox’s flattery. The fox, however, is set on getting a second piece of cheese. This time , it chooses a more direct method and throws a stone at the crow to scare it. It works beyond expectations: as soon as the stone is thrown, the crow drops the cheese. The crow is perched on a tree of height H; the fox is a distance L from the

The hare and the turtle

A hare and a turtle race over a distance L. The turtle starts running at constant speed

v_{\rm t}

and the hare at constant speed

v_{\rm h}

. The hare is not taking this seriously, and so

v_{\rm h} < v_{\rm t}

. When the turtle reaches a bridge that stands at a distance L′u2004

Related notebooks (6)

Designing FIR Filters Using the Parks-McClellan Algorithm

The Parks-McClellan Filter Design Method[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

The Parks-McClellan (PM) algorithm is a clever application of advanced polynomial fitting techniques to the problem of FIR filter design. In this notebook we will explore the key ideas behind the method by considering the design of a simple Type-I lowpass filter. NOTE: This notebook uses interactive widgets. If the interactive controls do not work or show up, please fo

Numerical Precision in DFT Computation

Numerical Precision in DFT Computation[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In [1]:

first our usual bookkeeping

%matplotlib inline import matplotlib import matplotlib.pyplot as plt import numpy as np In this notebook we will look at some numerical issues associated to the DFT; in particular we we will look at the differences in precision between the "naive" way of computing the DFT and the FFT algorithm. As a quick reminder, the definitions of t

Building a Dual-Tone Multi-Frequency (DTMF) Decoder using Short-Time Fourier Transform

Dual-tone multi-frequency (DTMF) signaling[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will build a dual-tone multi-frequency decoder based on the short-time Fourier transform. In [1]:

first our usual bookkeeping

%matplotlib inline import matplotlib import matplotlib.pyplot as plt import numpy as np import IPython In [2]: plt.rcParams["figure.figsize"] = (14,4)

Introduction[4]¶ DTMF signaling is the way analog phones send the n

Exploring Quantization and Oversampling through One-Bit Music

One-Bit Music[1]¶ In this notebook we will talk about quantization and oversampling and we will do so by taking a trip down memory lane to revisit the early from monophonic square waves, introduce polyphony by way of pulse-width modulation and finish with the basics of sigma-delta quantization. pacman In [1]: import matplotlib import matplotlib.pyplot as plt import numpy as np import scipy.signal as sp from scipy.io import wavfile import IPython In [2]: import sys ! wget -q -O mus

Voice Transformation Techniques Using Digital Signal Processing

A Gallery of Voice Transformers[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will explore various ways to implement a system that changes the voice of a speaker. Typical applications for these techniques, strictly sorted by plausibility, include international spy missions and prank telephone calls, and devices such as the one displayed here can be easily bought on the web... or in a novelty shop. No description has been provided for t

Related people (32)

Related exercises (32)

Gauss s law for magnetism

A Gaussian surface in the shape of a right circular cylinder has a radius of 13u2006cm and a length of 80u2006cm. Through one end there is an inward magnetic flux of 25u2006μWb, where

1\,{\rm Wb\,(Weber)} = 1\,{\rm T}\cdot {\rm m}^2

The crow and the fox

The hare and the turtle

A hare and a turtle race over a distance L. The turtle starts running at constant speed

v_{\rm t}

and the hare at constant speed

v_{\rm h}

. The hare is not taking this seriously, and so

v_{\rm h} < v_{\rm t}

. When the turtle reaches a bridge that stands at a distance L′u2004

Related notebooks (6)

Designing FIR Filters Using the Parks-McClellan Algorithm

The Parks-McClellan Filter Design Method[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

Numerical Precision in DFT Computation

Numerical Precision in DFT Computation[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In [1]:

first our usual bookkeeping

Building a Dual-Tone Multi-Frequency (DTMF) Decoder using Short-Time Fourier Transform

Dual-tone multi-frequency (DTMF) signaling[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will build a dual-tone multi-frequency decoder based on the short-time Fourier transform. In [1]:

first our usual bookkeeping

%matplotlib inline import matplotlib import matplotlib.pyplot as plt import numpy as np import IPython In [2]: plt.rcParams["figure.figsize"] = (14,4)

Introduction[4]¶ DTMF signaling is the way analog phones send the n

Exploring Quantization and Oversampling through One-Bit Music

Voice Transformation Techniques Using Digital Signal Processing

A Gallery of Voice Transformers[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL