Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Constraint Satisfaction Problem - What Makes the Problem Easy

International Mathematical Union via YouTube

Overview

Explore the intricacies of constraint satisfaction problems in this 43-minute lecture by Dmitriy Zhuk, presented at the International Mathematical Union. Delve into the world of combinatorial problems, such as graph coloring and solving linear equations, and learn how they can be expressed as constraint satisfaction problems for various constraint languages. Examine the proof of a famous conjecture that states any constraint language problem is either solvable in polynomial time or NP-complete. Investigate other variants of this problem with unknown complexity, including those involving universal and existential quantifiers or requiring additional conditions for input or solutions. Access the accompanying presentation slides for a comprehensive visual aid to enhance your understanding of this complex mathematical topic.

Syllabus

Dmitriy Zhuk: Constraint Satisfaction Problem: what makes the problem easy

Taught by

International Mathematical Union

Reviews

Start your review of Constraint Satisfaction Problem - What Makes the Problem Easy

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.