On the descriptive complexity of phylogeny constraint satisfaction problems

Abstract

Auf den Blättern eines Wurzelbaums ist die ternäre Relation C definiert durch C(x, y, z) genau dann wenn der jüngste gemeinsame Vorfahre von x, y und z strikt näher bei der Wurzel liegt als der jüngste gemeinsame Vorfahre von y und z. Ein phylogenetisches Problem ist ein Berechnungsproblem, dessen Instanzen Instanziierungen einer fixen Menge Boolescher Kombinationen von Formeln der Form C(x, y, z) oder x = y sind; die Frage ist, ob es einen Wurzelbaum und eine Abbildung von den Variablen auf die Blätter dieses Baumes gibt, sodass alle Formeln erfüllt sind. Jedes phylogenetische Problem entspricht einem Bedingungserfüllungsproblem (engl. Constraint Satisfaction Problem, kurz CSP) einer speziellen unendlichen Struktur, die ω-kategorisch und in den wichtigsten Fällen auch homogen ist. Es ist bekannt, dass ein phylogenetisches CSP in P liegt, wenn diese Struktur eine bestimmte algebraische Eigenschaft aufweist; andernfalls ist es NP-vollständig. In dieser Arbeit wollen wir die deskriptive Komplexität solcher Probleme untersuchen, insbesondere ihre Ausdrückbarkeit in Fixpunktlogiken. Einerseits präsentieren wir ein phylogenetisches Problem, das zwar in P liegt, sich aber nicht in Fixpunktlogik ausdrücken lässt, nicht einmal in der Erweiterung durch Zählquantoren. Andererseits führen wir Boolesche Hornformeln ein; dabei handelt es sich um eine syntaktische Einschränkung von affinen Hornformeln. Wir zeigen, dass alle phylogenetischen CSPs, die eine Vorlage haben, deren Relationen sich mittels Booleschen Hornformeln definieren lassen, in Fixpunktlogik ausdrückbar sind. Außerdem gibt es eine spezielle Struktur, die alle solchen Strukturen pp-definiert. Unter einer zusätzlichen Bedingung sind diese Strukturen genau die, die von einem bestimmten Polymorphismus bewahrt werden.

On the leafs of a rooted tree, the ternary relation C is given by C(x, y, z) if and only if the youngest common ancestor of x, y and z is strictly closer to the root than the youngest common ancestor of y and z. A phylogeny problem is a computational decision problem whose instances are instantiations of a fixed set of Boolean combinations of formulas of the form C(x, y, z) and x = y; the question is whether there is a rooted tree and a mapping from the variables to the leaves of the tree such that all formulas are satisfied. Each phylogeny problem corresponds with a constraint satisfaction problem (CSP) of a specific infinite structure, which is ω-categorical and in the most important cases also homogeneous. It has been shown that a phylogeny CSP is in P if this structure fulfilles a certain algebraic condition, and NP-complete otherwhise. In this thesis, we want to study the descriptive complexity of such problems, especially their expressibility in fixed point logics. On the one hand, we present a phylogeny problem which is tractable, but inexpressiblein fixed point logic, even with counting. On the other hand, we introduce Boolean Horn formulas; they are a further syntactic restriction of affine Horn formulas. It turns out that all phylogeny CSPs with a template whose relations can be defined by Boolean Horn formulas are expressible in fixed point logic. Moreover, there is a specific structure which pp-defines all such structures. Under an additional assumption, those structures are characterized as being preserved by a specific polymorphism.