Sign inSign in

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.
as Pieter Abbeel defines itUC BerkeleyThe wording closest to all 9 definitions
Watch it explained

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

5

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    Mathematical problems defined as a set of variables that must take values in a specified domain that satisfies a number of constraints.
    • 0:09Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
    • 0:33Constraint Satisfaction Problems
    • 2:19Constraint Satisfaction Problems
    • 1:10:19Probabilistically Checkable Proofs of Proximity
  • Pieter Abbeel

    UC Berkeley · Undergraduate

    • 3:55Constraint Satisfaction Problems (CSPs) Part 1/2
  • Brian Yu

    Harvard University · Undergraduate

    A problem consisting of variables with domains of values, subject to constraints that limit what values those variables can take on.
    • 6:25:26Harvard CS50’s Artificial Intelligence with Python – Full University Course
  • Avi Wigderson

    Institute for Advanced Study · Undergraduate

    A class of problems where variables take values from a domain subject to constraints specified by relations.
    • 25:35Mathematics and Computation: The Landscape of P vs. NP
  • Marvin Kunneman

    Max Planck Institute for Informatics · Research

    A class of problems inside NP where one seeks to find values for variables that satisfy a given set of constraints.
    • 6:42A Fine-Grained Analogue of Schaefer's Theorem in P

Lectures that assume it

12

Connections

31

The lectures that define it or assume it, and the concepts next to it.

Concepts10

Show 4 more

Lectures21

Show 15 more

5 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.