Halting Problem: P vs NP

This lecture explores the halting problem, demonstrating the undecidability of determining if a program halts when executed with itself as input. It delves into the complexity theory, discussing the class P for problems solvable in polynomial time, contrasting with the NP class for non-deterministic polynomial problems. The lecture also covers practical algorithms, complexity measurement, and examples of problems in P and NP. It concludes with a discussion on the Traveling Salesman and Knapsack problems, illustrating the challenges of finding optimal solutions within NP complexity.

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 lectures (49)

Related concepts (46)

CS-119(c): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (

Socialist calculation debate

The socialist calculation debate, sometimes known as the economic calculation debate, was a discourse on the subject of how a socialist economy would perform economic calculation given the absence of the law of value, money, financial prices for capital goods and private ownership of the means of production. More specifically, the debate was centered on the application of economic planning for the allocation of the means of production as a substitute for capital markets and whether or not such an arrangement would be superior to capitalism in terms of efficiency and productivity.

Calculation in kind

NOTOC Calculation in kind or calculation in-natura is a way of valuating resources and a system of accounting that uses disaggregated physical magnitudes as opposed to a common unit of calculation. As the basis for a socialist economy, it was proposed to replace money and financial calculation. In an in-kind economy products are produced for their use values (their utility) and accounted in physical terms. By contrast, in money-based economies, commodities are produced for their exchange value and accounted in monetary terms.

Quantum complexity theory

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA.

Economic calculation problem

The economic calculation problem (sometimes abbreviated ECP) is a criticism of using economic planning as a substitute for market-based allocation of the factors of production. It was first proposed by Ludwig von Mises in his 1920 article "Economic Calculation in the Socialist Commonwealth" and later expanded upon by Friedrich Hayek. In his first article, Mises described the nature of the price system under capitalism and described how individual subjective values (while criticizing other theories of value) are translated into the objective information necessary for rational allocation of resources in society.

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.

Theory of Computability: Solvability and Complexity

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

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Elements of Computational Complexity PHYS-641: Quantum Computing

Introduces computational complexity, decision problems, quantum complexity, and probabilistic algorithms, including NP-hard and NP-complete problems.

Complex Systems: Critical Phenomena PHYS-435: Statistical physics III

Explores critical phenomena in complex systems, including stochastic objects, percolation, and combinatorial optimization.

P vs NP: Complexity Theory CS-119(c): Information, Computation, Communication

Delves into complexity theory, focusing on the P vs NP problem and the classification of computational problems based on efficiency.