{Symmetry, Logic, Constraint Satisfaction Problem}

on YouTube ↗54m

" summary

Fixed-template finite-domain CSPs are hard exactly when they lack the right algebraic symmetries: existence of a nontrivial polymorphism clone (equivalently failure to admit a reduction from 3SAT via PP-interpretation) predicts tractability. Concrete tools: affine polymorphisms give small generating sets and Gaussian-elimination–style algorithms; Maltsev/majority polymorphisms yield polynomial local-generation and bounded width (singleton arc consistency suffices); absence of such identities yields NP-completeness. Extensions cover weighted polymorphisms for optimization, oligomorphic infinite templates, and open goals like an LP-unifying criterion and algebraic markers for undecidability.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 3:03CSP over fixed finite template
3. 6:08Examples and a conjecture
4. 8:07Selected results
5. 11:17Example of simulation (gadget reduction, pp-definition)
6. 13:001 reason for hardness
7. 16:03Too popular viewpoint
8. 17:45Alternative viewpoint
9. 25:57Expressive power and polymorphisms
10. 28:20Tractability conjecture again Tractability conjecture
11. 29:39Tractability conjecture vs. reality
12. 37:51Describing all solutions 2
13. 43:59Beyond
14. 48:57How far?