Author name cluster

Michael Kompatscher

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

MFCS Conference 2023 Conference Paper

Short Definitions in Constraint Languages

Jakub Bulín
Michael Kompatscher

A first-order formula is called primitive positive (pp) if it only admits the use of existential quantifiers and conjunction. Pp-formulas are a central concept in (fixed-template) constraint satisfaction since CSP(Γ) can be viewed as the problem of deciding the primitive positive theory of Γ, and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages Γ is characterized by having few subpowers, that is, the number of n-ary relations pp-definable from Γ is bounded by 2^p(n) for some polynomial p(n). In this paper we study a restriction of this property, stating that every pp-definable relation is definable by a pp-formula of polynomial length. We conjecture that the existence of such short definitions is actually equivalent to Γ having few subpowers, and verify this conjecture for a large subclass that, in particular, includes all constraint languages on three-element domains. We furthermore discuss how our conjecture imposes an upper complexity bound of co-NP on the subpower membership problem of algebras with few subpowers.

Details

FLAP Journal 2018 Journal Article

A Complexity Dichotomy for Poset Constraint Satisfaction.

Michael Kompatscher
Trung Van Pham

In this paper we determine the complexity of a broad class of problems that extend the temporal constraint satisfaction problems classified by Bodirsky and Kára. To be more precise, we study problems Poset-SAT(Φ) where Φ is a given set of quantifier-free ≤-formulas. An instance of Poset-SAT(Φ) then consists of finitely many variables and constraints on them expressible in Φ; the question is then whether this input can be satisfied in some partial order or not. We show that every such problem is either NP-complete or in P, depending on the constraint language Φ. All Poset-SAT problems can be formalized as constraint satisfaction problems of reducts of the random partial order. We use model-theoretic concepts and techniques from universal algebra to study these reducts. In the course of this analysis we establish a dichotomy that we believe is of independent interest in universal algebra and model theory.

PDF Details