ConceptTheory & Algos
Constraint satisfaction problem
A problem defined by variables, domains, and constraints, where the goal is to find an assignment of values to variables that satisfies all constraints.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Predicate3Search problem3Variable3Domain2Algorithm1Complexity classes1Complexity classes P and NP1Complexity theory1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
5Each in their own terms, from the easiest level.
Ryan O'Donnell
Mathematical problems defined as a set of variables that must take values in a specified domain that satisfies a number of constraints.Pieter Abbeel
Brian Yu
A problem consisting of variables with domains of values, subject to constraints that limit what values those variables can take on.Avi Wigderson
A class of problems where variables take values from a domain subject to constraints specified by relations.Marvin Kunneman
A class of problems inside NP where one seeks to find values for variables that satisfy a given set of constraints.
Lectures that assume it
12- The Sherali-Adams Proof System
- Constraints: Search and Domain Reduction
- Håstad's Hardness Theorems
- CSP Approximability: Optimization and Certification
- NP-Hardness of Approximation
- Dinur's Proof of the PCP Theorem: Outline
- Dinur's Proof of the PCP Theorem: The Powering Step
- UG-Hardness Results from Dictator Tests
- Trees and Series-Parallel Graphs
- Statement of the PCP Theorem
- Majority Is Stablest Theorem
- Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP
Connections
31The lectures that define it or assume it, and the concepts next to it.
Concepts10
Show 4 moreShow fewer
Lectures21
- Harvard CS50’s Artificial Intelligence with Python – Full University Course
- Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- Constraint Satisfaction Problems
- Constraint Satisfaction Problems (CSPs) Part 1/2
- Mathematics and Computation: The Landscape of P vs. NP
- Constraint Satisfaction Problems (CSPs) Part 2/2
Show 15 moreShow fewer
- A Fine-Grained Analogue of Schaefer's Theorem in P
- Constraint Satisfaction Problems
- Probabilistically Checkable Proofs of Proximity
- The Sherali-Adams Proof System
- Constraints: Search and Domain Reduction
- Håstad's Hardness Theorems
- CSP Approximability: Optimization and Certification
- NP-Hardness of Approximation
- Dinur's Proof of the PCP Theorem: Outline
- Dinur's Proof of the PCP Theorem: The Powering Step
- UG-Hardness Results from Dictator Tests
- Trees and Series-Parallel Graphs
- Statement of the PCP Theorem
- Majority Is Stablest Theorem
- Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP