104.611 AKINF AKALG The Constraint Satisfaction Problem dichotomy
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2022S, SE, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: SE Seminar
  • Format: Presence

Learning outcomes

After successful completion of the course, students are able to apply the Zhuk algorithm to solve finite domain CSPs.

Literature: D.Zhuk, A proof of the CSP dichotomy conjecture, https://arxiv.org/abs/1704.01914

Subject of course

Constraint Satisfaction Problems are computational problems where we are given variables and constraints, and where we are to decide whether there exist values for the variables satisfying all the constraints. Bulatov and Zhuk showed in 2017 that if the allowed values range in a fixed finite set, then such problems are always either solvable in polynomial time or NP-complete. We discuss Zhuk's algorithm which implies this result.

Teaching methods

Lectures.

Mode of examination

Immanent

Additional information

Please consider the plagiarism guidelines of TU Wien when writing your seminar paper: Directive concerning the handling of plagiarism (PDF)

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Wed15:00 - 16:0002.03.2022 Besprechungszimmer FH grün 5. StockPreliminary meeting
Wed11:00 - 13:0023.03.2022 - 29.06.2022Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
AKINF AKALG The Constraint Satisfaction Problem dichotomy - Single appointments
DayDateTimeLocationDescription
Wed02.03.202215:00 - 16:00 Besprechungszimmer FH grün 5. StockPreliminary meeting
Wed23.03.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed30.03.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed06.04.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed27.04.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed04.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed11.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed18.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed25.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed01.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed08.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed15.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed22.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Wed29.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy

Examination modalities

Continuous assessment.

Course registration

Begin End Deregistration end
23.02.2022 12:00 01.04.2022 12:00 01.04.2022 12:00

Curricula

Literature

No lecture notes are available.

Language

English