Placing problems from phylogenetics and (quantified) propositional logic in the polynomial hierarchy

DSpace Repositorium (Manakin basiert)

Zur Kurzanzeige

dc.contributor.advisor Dorn, Britta (Apl. Prof. Dr.)
dc.contributor.author Döcker, Janosch Otto
dc.date.accessioned 2021-09-09T09:31:52Z
dc.date.available 2021-09-09T09:31:52Z
dc.date.issued 2021-09-09
dc.identifier.uri http://hdl.handle.net/10900/118702
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-dspace-1187027 de_DE
dc.identifier.uri http://dx.doi.org/10.15496/publikation-60076
dc.description.abstract In this thesis, we consider the complexity of decision problems from two different areas of research and place them in the polynomial hierarchy: phylogenetics and (quantified) propositional logic. In phylogenetics, researchers study the evolutionary relationships between species. The evolution of a particular gene can often be represented by a single phylogenetic tree. However, in order to model non-tree-like events on a species level such as hybridization and lateral gene transfer, phylogenetic networks are used. They can be considered as a structure that embeds a whole set of phylogenetic trees which is called the display set of the network. There are many interesting questions revolving around display sets and one is often interested in the computational complexity of the considered problems for particular classes of networks. In this thesis, we present our results for different questions related to the display sets of two networks and place the corresponding decision problems in the polynomial hierarchy. Another interesting question concerns the reconstruction of networks: given a set T of phylogenetic trees, can we construct a phylogenetic network with certain properties that embeds all trees in T? For a class of networks that satisfies certain temporal properties, Humphries et al. (2013) established a characterization for when this is possible based on the existence of a particular structure for T, a so-called cherry-picking sequence. We obtain several complexity results for the existence of such a sequence: Deciding the existence of a cherry-picking sequence turns out to be NP-complete for each non-trivial number (i.e., at least two) of given trees. Thereby, we settle the open question stated by Humphries et al. (2013) on the complexity for the case |T| = 2. On the positive side, we identify a special case that we place in the complexity class P by exploring connections to automata theory. Regarding propositional logic, we present our complexity results for the classical satisfiability problem (and variants resp. quantified generalizations thereof) and place the considered variants in the polynomial hierarchy. A common theme is to consider bounded variable appearances in combination with other restrictions such as monotonicity of the clauses or planarity of the incidence graph. This research was inspired by the conjecture that Monotone 3-SAT remains NP-complete if each variable appears at most five times which was stated in the scribe notes of a lecture held by Erik Demaine; we confirm this conjecture in an even more restricted setting where each variable appears exactly four times. en
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-podno de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_ohne_pod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_ohne_pod.php?la=en en
dc.subject.classification Berechnungskomplexität , Entscheidungsproblem , Phylogenetik , Aussagenlogik , Boolesche Formel , Erfüllbarkeitsproblem de_DE
dc.subject.ddc 004 de_DE
dc.subject.other Polynomialzeithierarchie de_DE
dc.subject.other Polynomial hierarchy en
dc.title Placing problems from phylogenetics and (quantified) propositional logic in the polynomial hierarchy en
dc.type PhDThesis de_DE
dcterms.dateAccepted 2021-06-23
utue.publikation.fachbereich Informatik de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
utue.publikation.noppn yes de_DE

Dateien:

Das Dokument erscheint in:

Zur Kurzanzeige