Technische Berichte

• Till Tantau:
  On the Power of Extra Queries to Selective Languages.
  Technischer Bericht ECCC-TR00-077, Electronic Colloquium on Computational Complexity, 2000.
  Website anzeigen | Zusammenfassung anzeigen
  
  A language is selective if there exists a selection algorithm for it. Such an algorithm selects from any two words one, which is an element of the language whenever at least one of them is. Restricting the complexity of selection algorithms yields different selectivity classes like the P-selective or the semirecursive (i.e. recursively selective) languages. A language is supportive if k queries to the language are more powerful than k-1 queries for every k. Recently, Beigel et al. (J. of Symb. Logic, 65(1):1-18, 2000) proved a powerful recursion theoretic theorem: A semirecursive language is supportive iff it is nonrecursive. For restricted computational models like polynomial time this theorem does not hold in this form. Our main result states that for any reasonable computational model a selective language is supportive iff it is not cheatable. Beigel et al.'s result is a corollary of this general theorem since `recursively cheatable' languages are recursive by Beigel's Nonspeedup Theorem. Our proof is based on a partial information analysis (see Nickelsen, STACS 97, LNCS 1200, pp. 307-318) of the involved languages: We establish matching upper and lower bounds for the partial information complexity of the equivalence and reduction closures of selective languages. From this we derive the main results as these bounds differ for different k.

  We give four applications of our main theorem and the proof technique. Firstly, the relation E^P_k-tt(P-sel) \notsubseteq R^P_(k-1)-tt(P-sel) proven by Hemaspaandra et al. (Theor. Comput. Sci., 155(2):447-457, 1996) still holds if we relativise only the right hand side. Secondly, we settle an open problem from the same paper: Equivalence to a P-selective language with k serial queries cannot generally be replaced by a reduction using less than 2^k-1 parallel queries. Thirdly, the k-truth-table reduction closures of selectivity classes are (m,n)-verbose iff every walk on the n-dimensional hypercube with transition counts at most k visits at most m bitstrings. Lastly, these reduction closures are (m,n)-recursive iff every such walk is contained in a closed ball of radius n-m.

• Till Tantau:
  A Note on the Complexity of the Reachability Problem for Tournaments.
  Technischer Bericht ECCC-TR01-092, Electronic Colloquium on Computational Complexity, 2001.
  Website anzeigen | Zusammenfassung anzeigen
  
  Deciding whether a vertex in a graph is reachable from another vertex has been studied intensively in complexity theory and is well understood. For common types of graphs like directed graphs, undirected graphs, dags or trees it takes a (possibly nondeterministic) logspace machine to decide the reachability problem, and the succinct versions of these problems (which often arise in hardware design) are all PSPACE-complete. In this paper we study tournaments, which are directed graphs with exactly one edge between any two vertices. We show that the tournament reachability problem is first order definable and that its succinct version is \Pi^P₂-complete.
• Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
  Computation with Absolutely No Overhead.
  Technischer Bericht URCS-TR-2002-779, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
  Website anzeigen | Zusammenfassung anzeigen
  
  We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that a large subclasses of the context-free languages can even be accepted in polynomial time with absolutely no space overhead.
• Mitsunori Ogihara, Till Tantau:
  On the Reducibility of Sets Inside NP to Sets with Low Information Content.
  Technischer Bericht URCS-TR-2002-782, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
  Website anzeigen | Zusammenfassung anzeigen
  
  We study whether sets inside NP can be reduced to sets with low information content but possibly still high computational complexity. Examples of sets with low information content are tally sets, sparse sets, P-selective sets and membership comparable sets. For the graph automorphism and isomorphism problems GA and GI, for the directed graph reachability problem GAP, for the determinant function det, and for logspace self-reducible languages we establish the following results:

  • If GA is \le^p_tt-reducible to a P-selective set, then GA \in P.
  • If GI is O(log)-membership comparable, then GI \in RP.
  • If GAP is logspace O(1)-membership comparable, then GAP \in L.
  • If det is \le^log_T-reducible to an L-selective set, then det \in FL.
  • If A is logspace self-reducible and \le^log_T-reducible to an L-selective set, then A \in L.

  The last result is a strong logspace version of the characterisation of P as the class of self-reducible P-selective languages. As P and NL have logspace self-reducible complete sets, it also establishes a logspace analogue of the conjecture that if SAT is \le^p_T-reducible to a P-selective set, then SAT \in P.
• Till Tantau:
  A Note on the Power of Extra Queries to Membership Comparable Sets.
  Technischer Bericht ECCC-TR02-044, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
  Website anzeigen | Zusammenfassung anzeigen
  
  A language is called k-membership comparable if there exists a polynomial-time algorithm that excludes for any k words one of the 2^k possibilities for their characteristic string. It is known that all membership comparable languages can be reduced to some P-selective language with polynomially many adaptive queries. We show however that for all k there exists a (k+1)-membership comparable set that is neither truth-table reducible nor sublinear Turing reducible to any k-membership comparable set. In particular, for all k > 2 the number of adaptive queries to P-selective sets necessary to decide all k-membership comparable sets is Omega(n) and O(n³). As this shows that the truth-table closure of P-sel is a proper subset of P-mc(log), we get a proof of Sivakumar's conjecture that O(log)-membership comparability is a more general notion than truth-table reducibility to P-sel.
• Till Tantau:
  Logspace Optimisation Problems and Their Approximation Properties.
  Technischer Bericht ECCC-TR03-077, Electronic Colloquium on Computational Complexity, 2003.
  Website anzeigen | Zusammenfassung anzeigen
  
  This paper introduces logspace optimisation problems as an analogue of the widely studied polynomial-time optimisation problems. Similarly to the polynomial-time setting, logspace optimisation problems can have vastly different approximation properties, even though the underlying decision problems have the same computational complexity. In order to study the approximability of logspace optimisation problems in a systematic way, polynomial-time approximation classes are transferred to logarithmic space. Appropriate reductions are defined and optimisation problems are presented that are complete for these classes. It is shown that under the assumption L != NL some natural logspace optimisation problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but cannot be solved in logarithmic space. An example of a problem of the latter type is the problem of finding the shortest path between two vertices of a tournament.
• Till Tantau:
  Weak Cardinality Theorems for First-Order Logic.
  Technischer Bericht ECCC-TR03-024, Electronic Colloquium on Computational Complexity, 2003.
  Website anzeigen | Zusammenfassung anzeigen
  
  Kummer's cardinality theorem states that a language is recursive if a Turing machine can exclude for any n words one of the n + 1 possibilities for the number of words in the language. It is known that this theorem does not hold for polynomial-time computations, but there is evidence that it holds for finite automata: at least weak cardinality theorems hold for finite automata. This paper shows that some of the recursion-theoretic and automata-theoretic weak cardinality theorems are instantiations of purely logical theorems. Apart from unifying previous results in a single framework, the logical approach allows us to prove new theorems for other computational models. For example, weak cardinality theorems hold for Presburger arithmetic.
• Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
  Overhead-Free Computation, DCFLs, and CFLs.
  Technischer Bericht URCS-TR-2004-844, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2004.
  Website anzeigen | Zusammenfassung anzeigen
  
  We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.
• Arfst Nickelsen, Till Tantau, Lorenz Weizäcker:
  Aggregates with Component Size One Characterize Polynomial Space.
  Technischer Bericht ECCC-TR04-028, Electronic Colloquium on Computational Complexity, 2004.
  Website anzeigen | Zusammenfassung anzeigen
  
  Aggregates are a computational model similar to circuits, but the underlying graph is not necessarily acyclic. Logspace-uniform polynomial-size aggregates decide exactly the languages in PSPACE; without uniformity condition they decide the languages in PSPACE/poly. As a measure of similarity to boolean circuits we introduce the parameter component size. We prove that already aggregates of component size 1 are powerful enough to capture polynomial space. The only type of cyclic components needed to make polynomial-size circuits as powerful as polynomial-size aggregates are binary xor-gates whose output is fed back to the gate as one of the inputs.
• Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
  On the Complexity of Kings.
  Technischer Bericht URCS-TR905, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2006.
  Website anzeigen | Zusammenfassung anzeigen
  
  A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king [Lan53]. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems [Tan01,NT05]. and semifeasible sets [HNP98,HT06,HOZZ06]. In this paper, we study the complexity of recognizing kings. For each succinctly specified family of tournaments, the king problem is already known to belong to $\Pi_2^p$ [HOZZ06]. We prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in $\Pi_2^p$. That is, we show that \emph{every} set in $\Pi_2^p$ other than $\emptyset$ and $\Sigma^*$ is equivalent to a king problem under $\leq_m^p$-reductions. Indeed, we show that the equivalence can even be instantiated via relatively simple padding, and holds even if the notion of kings is redefined to refer to k-kings (for any fixed $k \geq 2$)---nodes from which the all nodes can be reached via paths of length at most k. Using these and related techniques, we obtain a broad range of additional results about the complexity of king problems, diameter problems, radius problems, and initial component problems. It follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is $\Pi_2^p$-complete. We show that the radius problem for arbitrary succinctly represented graphs is $\Sigma_3^p$-complete, but that in contrast the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is $\Pi_2^p$-complete. Yet again in contrast, we prove that initial component languages (which ask whether a given node can reach all other nodes in its tournament) all fall within $\Pi_2^p$, yet cannot be $\Pi_2^p$-complete---or even NP-hard---unless P=NP.
• Till Tantau:
  The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
  Technischer Bericht ECCC-TR06-035, Electronic Colloquium on Computational Complexity, 2006.
  Website anzeigen | Zusammenfassung anzeigen
  
  The reachability problem for graphs cannot be described, in the sense of descriptive complexity theory, using a single first-order formula. This is true both for directed and undirected graphs, both in the finite and infinite. However, if we restrict ourselves to graphs in which a certain graph parameter is fixed to a certain value, first-order formulas often suffice. A trivial example are graphs whose number of vertices is fixed to n. In such graphs reachability can be described using a first-order formula with a quantifier nesting depth of log₂ n, which is both a lower and an upper bound. In this paper we investigate how the descriptive complexity of the reachability problem varies as a function of graph parameters such as the size of the graph, the clique number, the matching number, the independence number or the domination number. The independence number turns out to be the by far most challenging graph parameter.
• Bodo Manthey, Till Tantau:
  Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
  Technischer Bericht ECCC-TR07-039, Electronic Colloquium on Computational Complexity, 2007.
  Website anzeigen | Zusammenfassung anzeigen
  
  Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. Their worst-case height is linear; their average height, whose exact value is one of the best-studied problems in average-case complexity, is logarithmic. We analyze their smoothed height under additive noise: An adversary chooses a sequence of n real numbers in the range [0,1]; each number is individually perturbed by adding a random value from an interval of size d; and the resulting numbers are inserted into a search tree. The expected height of this tree is called smoothed tree height. If d is very small, namely for d < 1/n, the smoothed tree height is the same as the worst-case height; if d is very large, the smoothed tree height approaches the logarithmic average-case height. An analysis of what happens between these extremes lies at the heart of our paper: We prove that the smoothed height of binary search trees is $Theta (sqrt{n/d} + log n)$, where d >= 1/n may depend on n. This implies that the logarithmic average-case height becomes manifest only for $d in Omega (n/log^2 n)$. For the analysis, we first prove that the smoothed number of left-to-right maxima in a sequence is also $Theta (sqrt{n/d} + log n)$. We apply these findings to the performance of the quicksort algorithm, which needs $Theta(n^2)$ comparisons in the worst case and $Theta(n log n)$ on average, and prove that the smoothed number of comparisons made by quicksort is $Theta(n/d+1 sqrt{n/d} + n log n)$. This implies that the average-case becomes manifest already for $d in Omega(sqrt[3]{n/logsqr n})$.
• Till Tantau:
  Complexity of the Undirected Radius and Diameter Problems for Succinctly Represented Graphs.
  Technischer Bericht SIIM-TR-A-08-03, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
  PDF anzeigen
• Till Tantau:
  Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.
  Technischer Bericht ECCC-TR08-027, Electronic Colloquium on Computational Complexity, 2008.
  PDF anzeigen | Zusammenfassung anzeigen
  
  The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets: 1. E = UE if, and only if, all functions f: {1}^* to Sigma^* in NPSV_g lie in FP. 2. E = NE if, and only if, all functions f: {1}^* to Sigma^* in NPFewV lie in FP. 3. E = E^NP if, and only if, all functions f: {1}^* to Sigma^* in OptP lie in FP. 4. E = E^NP if, and only if, all standard left cuts in NP lie in P. 5. E = EH if, and only if, PH cap P/poly = P. We apply these results to the immunity of P-selective sets. It is known that they can be bi-immune, but not Pi_2^p/1-immune. Their immunity is closely related to top-Toda languages, whose complexity we link to the exponential realm, and also to king languages. We introduce the new notion of superkings, which are characterized in terms of existsforall-predicates rather than forallexists-predicates, and show that king languages cannot be Sigma_2^p-immune. As a consequence, P-selective sets cannot be Sigma_2^/1-immune and, if E^NP^NP = E, not even P/1-immune.
• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Technischer Bericht , Electronic Colloquium on Computational Complexity, 2019.
  Website anzeigen | Zusammenfassung anzeigen
  
  Computing kernels for the hitting set problem (the problem of finding a size-$k$ set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with $m$ hyperedges, each of size at most~$d$, the best algorithms can compute kernels of size $O(k^d)$ in time $O(2^d m)$. In this paper we generalize the task to the \emph{dynamic} setting where hyperedges may be continuously added and deleted and we always have to keep track of a hitting set kernel (including moments when no size-$k$ hitting set exists). We present a deterministic solution, based on a novel data structure, that needs worst-case time $O^*(3^d)$ for updating the kernel upon hyperedge inserts and time~$O^*(5^d)$ for updates upon deletions -- thus nearly matching the time $O^*(2^d)$ needed by the best static algorithm per hyperedge. As a novel technical feature, our approach does not use the standard replace-sunflowers-by-their-cores methodology, but introduces a generalized concept that is actually easier to compute and that allows us to achieve a kernel size of $\sum_{i=0}^d k^i$ rather than the typical size $d!\cdot k^d$ resulting from the Sunflower Lemma. We also show that our approach extends to the dual problem of finding packings in hypergraphs (the problem of finding $k$ pairwise disjoint hyperedges), albeit with a slightly larger kernel size of $\sum_{i=0}^d d^i(k-1)^i$.
• Malte Skambath, Till Tantau:
  Offline Drawing of Dynamic Trees: Algorithmics and Document Integration Analysis of Binary Search Trees.
  Technischer Bericht arXiv:1608.08385, CoRR, 2016.
  Website anzeigen | Zusammenfassung anzeigen
  
  While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular TEX typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running TEX on the documents then results in documents in the SVG format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.
• Christoph Stockhusen, Till Tantau:
  Completeness Results for Parameterized Space Classes.
  Technischer Bericht arxiv:1308.2892, ArXiv, 2013.
  Website anzeigen | Zusammenfassung anzeigen
  
  The parameterized complexity of a problem is considered "settled" once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a "union operation" that translates between problems complete for classical complexity classes and for W-classes.
• Michael Elberfeld, Christoph Stockhusen, Till Tantau:
  On the Space Complexity of Parameterized Problems.
  Technischer Bericht , ECCC, 2012.
  Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  
  Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. We show that the undirected and the directed feedback vertex set problems have different parameterized space complexities, unless L=NL. For a number of further natural parameterized problems, including the longest common subsequence problem, the acceptance problem for multi-head automata, and the associative generability problem we show that they lie in or are complete for different parameterized space classes. Our results explain why previous attempts at proving completeness of different problems for parameterized time classes have failed.
• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
  Technischer Bericht ECCC-TR11-128, Electronic Colloquium on Computational Complexity, 2011.
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  An algorithmic meta theorem for a logic and a class C of structures states that all problems expressible in this logic can be solved efficiently for inputs from C. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded tree width. We contribute new algorithmic meta theorems, which state that MSO-definable problems are (a) solvable by uniform constant-depth circuit families (AC0 for decision problems and TC0 for counting problems) when restricted to input structures of bounded tree depth and (b) solvable by uniform logarithmic-depth circuit families (NC1 for decision problems and #NC1 for counting problems) when a tree decomposition of bounded width in term representation is part of the input. Applications of our theorems include a TC0-completeness proof for the unary version of integer linear programming with a fixed number of equations and extensions of a recent result that counting the number of accepting paths of a visible pushdown automaton lies in #NC1. Our main technical contributions are a new tree automata model for unordered, unranked, labeled trees; a method for representing the tree automata's computations algebraically using convolution circuits; and a lemma on computing balanced width-3 tree decompositions of trees in TC0, which encapsulates most of the technical difficulties surrounding earlier results connecting tree automata and NC1.
• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Logspace Versions of the Theorems of Bodlaender and Courcelle.
  Technischer Bericht ECCC-TR10-062, Electronic Colloquium on Computational Complexity, 2010.
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.
• Michael Elberfeld, Till Tantau:
  Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  Technischer Bericht SIIM-TR-A-10-01, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2010.
  PDF anzeigen | Zusammenfassung anzeigen
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolution- ary model where a perfect phylogenetic tree is sought that explains the observed data. In their CPM’09 paper, Fellows et al. studied an exten- sion of this approach that incorporates prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. While this approach is attractive to increase the accuracy of haplotyping methods, it was conjectured that the resulting formal prob- lem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption.
• Michael Elberfeld, Till Tantau:
  Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
  Technischer Bericht SIIM-TR-A-08-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
  PDF anzeigen | Zusammenfassung anzeigen
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. This problem, which has strong practical applications, can be approached using both statistical as well as combinatorial methods. While the most direct combinatorial approach, maximum parsimony, leads to NP-complete problems, the perfect phylogeny model proposed by Gusfield yields a problem, called PPH, that can be solved in polynomial (even linear) time. Even this may not be fast enough when the whole genome is studied, leading to the question of whether parallel algorithms can be used to solve the PPH problem. In the present paper we answer this question affirmatively, but we also give lower complexity bounds on its complexity. In detail, we show that the problem lies in Mod$_2$L, a subclass of the circuit complexity class NC$^2$, and is hard for logarithmic space and thus presumably not in NC$^1$. We also investigate variants of the PPH problem that have been studied in the literature, like the perfect path phylogeny haplotyping problem and the combined problem where a perfect phylogeny of maximal parsimony is sought, and show that some of these variants are TC$^0$-complete or lie in AC$^0$.
• Michael Elberfeld, Ilka Schnoor, Till Tantau:
  Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
  Technischer Bericht SIIM-TR-A-08-05, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
  PDF anzeigen | Zusammenfassung anzeigen
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing, as is often the case in real laboratory data, the resulting formal problem IPPH, which stands for incomplete perfect phylogeny haplotyping, is NP-complete and no theoretical results are known concerning its approximability, fixed-parameter tractability or exact algorithms for it. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP-complete, but here, at least, a fixed-parameter algorithm is known. We generalize this algorithm to arbitrary tree topologies and present the first theoretical analysis of an algorithm that works on arbitrary instances of the original IPPH problem. At the same time we also show that restricting the tree topology does not always make finding phylogenies easier: while the incomplete directed perfect phylogeny problem is well-known to be solvable in polynomial time, we show that the same problem restricted to path topologies is NP-complete.

Dissertationen

• Till Tantau:
  On Structural Similarities of Finite Automata and Turing Machine Enumerability Classes.
  Wissenschaft und Technik Verlag, 2003.
  Gutachter: Dirk Siefkes, Johannes Köbler. Disseration zum Dr. rer. nat., Technische Universität Berlin
  Zusammenfassung anzeigen
  
  Die Komplexit&auml;t von Funktionen, die Worte auf Worte abbilden, kann auf verschiedene Arten gemessen werden. Bekannte Ma&szlig;e sind Zeit- und Platzkomplexit&auml;t. <i>Aufz&auml;hlbarkeit</i> ist ein weiteres Komplexit&auml;tsma&szlig;. Sie wird in der Rekursionstheorie eingesetzt, wo sie eine zentrale Rolle in der Theorie fragenbeschr&auml;nkter Reduktionen spielt, sowie in der ressourcebeschr&auml;nkten Komplexit&auml;tstheorie, insbesondere in Verbindung mit nichtuniformen Berechnungen. In dieser Arbeit wird das Konzept der Aufz&auml;hlbarkeit auf endliche Automaten &uuml;bertragen. Es wird gezeigt, dass sich Aufz&auml;hlbarkeit in der Rekursionstheorie und in der Automatentheorie gleichartig verh&auml;lt, in der Komplexit&auml;tstheorie hingegen andersartig. </p> <p> Die Aufz&auml;hlbarkeit einer Funktion <i>f</i> ist die kleinste Zahl <i>m</i>, f&uuml;r die ein <i>m</i>-Aufz&auml;hler f&uuml;r <i>f</i> existiert. Ein <i>m-Aufz&auml;hler</i> ist eine Maschine, die bei Eingabe eines Wortes <i>w</i> eine Menge von h&ouml;chstens <i>m</i> M&ouml;glichkeiten f&uuml;r <i>f</i>(<i>w</i>) ausgibt. Verschiedene Klassen k&ouml;nnen durch Ver&auml;nderung des Parameters <i>m</i> und der Art der erlaubten Maschinen definiert werden. In der Rekursionstheorie erlaubt man beliebige Turingmaschinen als Aufz&auml;hler, in der Automatentheorie lediglich endliche Automaten. Ein tief liegendes strukturelles Resultat, das sowohl f&uuml;r Turingmaschinen als auch f&uuml;r endliche Automaten gilt, ist der folgende <i>Kreuzproduktsatz</i>: Ist <i>f &times; g</i> eine (<i>n</i> + <i>m</i>)-aufz&auml;hlbare Funktion, so ist entweder <i>f</i> eine <i>n</i>-aufz&auml;hlbare oder <i>g</i> eine <i>m</i>-aufz&auml;hlbare Funktion. Dieser Satz gilt nicht im Polynomialzeitfall. </p> <p> Aufz&auml;hlbarkeit kann auch benutzt werden, um die Komplexit&auml;t von <i>Sprachen</i> zu quantifizieren. Dazu wird gefragt, wie schwierig es ist, die <i>n</i>-fache charakteristische Funktion \chi<i>_Aⁿ</i> und die <i>n</i>-fache Kardinalit&auml;tsfunktion #<i>_Aⁿ</i> einer Sprache <i>A</i> aufzuz&auml;hlen. Eine Sprache <i>A</i> ist (<i>m</i>, <i>n</i>)<i>-verbose</i>, falls \chi<i>_Aⁿ</i> <i>m</i>-aufz&auml;hlbar ist. Die Inklusionsstrukturen der Verbosenessklassen von Turingmaschinen und der von endlichen Automaten sind \hbox{gleich}: alle (<i>m</i>, <i>n</i>)-Turing-verbosen Sprachen sind genau dann auch (<i>h</i>, <i>k</i>)-Turing-verbose, wenn alle in Bezug auf endliche Automaten (<i>m</i>, <i>n</i>)-verbosen Sprachen auch (<i>h</i>, <i>k</i>)-verbose sind. Dies gilt nicht im Polynomialzeitfall. </p> <p> Die Aufz&auml;hlbarkeit von #<i>_Aⁿ</i> ist in der Rekursionstheorie wohluntersucht. Kummers Kardinalit&auml;tssatz besagt, dass <i>A</i> rekursiv ist, falls #<i>_Aⁿ</i> von einer Turingmaschine <i>n</i>-aufz&auml;hlbar ist. Vermutlich gilt dieser Satz auch f&uuml;r endliche Automaten: zumindest der Nonspeedupsatz, der Kardinalit&auml;tssatz f&uuml;r zwei Worte und der eingeschr&auml;nkte Kardinalit&auml;tssatz gelten f&uuml;r endliche Automaten. Der Kardinalit&auml;tssatz gilt nicht im Polynomialzeitfall. </p> <p> Die Hauptbeweise in dieser Arbeit benutzen zwei Techniken, deren Einsatz auch in anderen Gebieten vielversprechend erscheint: generische Beweise und Zweigdiagonalisierung. Generische Beweise benutzen elementare Definitionen, ein Konzept aus der Logik, um Aufz&auml;hler zu definieren. Solche Beweise lassen sich auf alle Berechnungsmodelle anwenden, die unter elementaren Definitionen abgeschlossen sind. Dies ist f&uuml;r endliche Automaten der Fall, aber auch f&uuml;r die Presburger-Arithmetik und die Ordinalzahlarithmetik. Die zweite Technik ist eine neue Diagonalisierungsmethode, bei der Maschinen auf dem Kode der bisherigen Folge von Diagonalisierungsentscheidungen ausgetrickst werden und nicht auf ihrem eigenen Kode. Zweigdiagonalisierung ist nicht universell einsetzbar, aber wo sie eingesetzt werden kann, kann man mit ihrer Hilfe gegen Turingmaschinen mittels endlicher Automaten diagonalisieren. </p> <p> Die Resultate &uuml;ber Aufz&auml;hlbarkeitsklassen haben auch in anderen Gebieten Anwendungen, so bei Protokolltests mittels endlicher Automaten, bei Klassifikationsproblemen mit Beispielen und bei Trennbarkeitsfragen. Ein sch&ouml;nes Beispiel einer solchen Anwendung lautet wie folgt: Existieren regul&auml;r Obermengen von <i>A</i> &times; <i>A</i>, <i>A</i> &times; \bar <i>A</i>, und \bar <i>A</i> &times; \bar <i>A</i>, deren Schnitt leer ist, so ist <i>A</i> regul&auml;r.

Master- und Diplomarbeiten

• Till Tantau:
  Combinatorial Representations of Partial Information Classes and their Truth-Table Closures.
  Technische Universität Berlin, 1999. Diplomarbeit Informatik
  Zusammenfassung anzeigen
  
  Teilinformationsklassen sind eine Verallgemeinerung klassischer Komplexitätsklassen, bei denen Probleme nicht vollständig, sondern nur zum Teil gelöst werden. Es stellt sich heraus, daß dies in einer Reihe von Anwendungen ausreichend ist. Truth-Table-Reduktionen sind ein strukturanalytisches Hilfsmittel, das häufig verwendet wird, um die Stabilität und Kompliziertheit von Komplexitätsklassen zu quantifizieren.

  Viele in der Literatur untersuchte Spielarten der Teilinformation, so zum Beispiel semirekursive, p-selektive, cheatable oder auch approximierbare Sprachen, erweisen sich als Spezialfälle der allgemeinen Definition von Teilinformation. Da Teilinformationsklassen kombinatorisch repräsentiert werden können durch sogenannte Familien, können all diese Arten von Teilinformation verglichen werden, indem man die zugehörigen Familien vergleicht. Untersuchungen der Kombinatorik von Familien im ersten Teil der Arbeit ermöglichen es, neue Resultate bezüglich der zugehörigen Teilinformationsklassen zu erhalten. Ein solches Resultat ist eine Verallgemeinerung des Generalised Non-Speedup Theorems.

  Im zweiten Teil werden die Stabilität und Kompliziertheit von Teilinformationsklassen mit Hilfe von Truth-Table-Reduktionsabschlüssen untersucht. Das Hauptresultat lautet, daß solche Abschlüsse ebenfalls rein kombinatorisch beschreibbar sind. Hierdurch wird das Inklusionsproblem für Truth-Table-Abschlüsse auf endliche Kombinatorik zurückgeführt. Auch im zweiten Teil ergibt eine Analyse dieser Kombinatorik neue Resultate bezüglich der Truth-Table-Abschlüsse selbst. Unter anderem ergibt sich ein neuartiger Beiweis dafür, daß all beschränkten Reduktionsabschlüsse der p-selektiven Sprachen unterschiedlich sind.

• Till Tantau:
  Schnelle Löser für periodische Integralgleichungen mittels Matrixkompression und Mehrgitteriteration.
  Technische Universität Berlin, 2001. Diplomarbeit Mathematik
  Zusammenfassung anzeigen
  
  Diese Arbeit untersucht schnelle Löser für eine Klasse von periodischen Integralgleichungen. Solche Integralgleichungen treten in einer Reihe von Problemstellungen auf, so zum Beispiel beim Lösen dirichletscher Probleme oder der biharmonischen Gleichung. Die in den betrachteten Integralgleichungen vorkommenden Integrale sind alle von der gleichen Bauart: Es handelt sich um Faltungsintegrale, bei denen ein glatter Störterm berücksichtigt wird. Stellt man geeignete Forderungen an die Fourierkoeffizienten der Faltungskerne, so lassen sich die betrachteten Gleichungen eindeutig lösen. Für diesen Fall werden Verfahren zur schnellen Berechnung der Lösung untersucht. Hierbei bedeutet »schnell«, dass der Rechenaufwand proportional zum Aufwand einer schnellen Fouriertransformation ist. Unter Einsatz einer parallelen Architektur kann bei gleich bleibendem Arbeitsaufwand sogar eine logarithmische Rechenzeit erreicht werden. Die Berechnung der Lösung verläuft in drei Schritten. Im ersten Schritt werden die Eingabefunktionen diskretisiert. Als zweites wird ein spektrales Galerkinverfahren auf die diskretisierte Gleichung angewandt. Dabei entstehen große Systemmatrizen, die sich aber komprimieren lassen. Die Matrixkompression erlaubt es im dritten Schritt, die gesuchte Lösung durch eine Mehrgitteriteration asymptotisch optimal zu approximieren.