Algebra Seminar talk
2016-04-08
Michael Kompatscher
A complexity dichotomy for Poset-SAT
Abstract:
Let Phi be a finite set of quantifier-free formulas in the language of orders.
Then an instance of the computational problem Poset-SAT(Phi) consists of a
conjunction of equations and formulas from Phi. The task is to decide whether
there is a partial order that satisfies this conjunction. We show that
Poset-SAT(Phi) is NP-complete or solvable in polynomial time, depending on the
set Phi.
We first restate the Poset-SAT problems as constraint satisfaction problems of reducts of the random partial order. We then study these reducts, analysing their polymorphism clones with the help of methods developed by Bodirsky and Pinsker. In the course of this analysis we establish a structural dichotomy regarding the clones that corresponds to the complexity dichotomy.
This is a joint work with Trung Van Pham.