|zpravodaj ČSKI - leden 2017 [ pdf ]|
datum: 18.1.2017 v 10:00
název: Algebraic Approach to Valued CSP via Nonclassical Logics
přednášející: Rostislav Horčík (UI)
místo konání: UI, 2.patro, místnost č.318
souhrn: CSP provides a uniform framework to analyze and solve many combinatorial problems. Similarly valued CSP might be seen as a uniform framework to study a wide class of problems coming from combinatorial optimization such as Maximum Independent Set. A major research line in CSP tries to find a boundary between tractable and intractable problems. One of the most successful approaches to classify tractable problems is the algebraic one based on Geiger’s result characterizing pp-definability via polymorphisms. A similar approach was investigated also in valued CSP but only for problems using as a valuation structure the set of positive rational numbers extended with infinity endowed with the usual addition. We show that this approach can be taken to a wider setting by generalizing Geiger’s result. It turns out that valued CSP can be viewed as CSP over a non-classical logic. Consequently, we obtain the generalization of Geiger’s result by characterizing ppdefinability in relational structures over this logic.