05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

2015 - 201912020 - 20222

Settings

Institute: search.filters.UBSInstitut.Institut für Formale Methoden der InformatikSubject: search.filters.subject.510

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    The Generalized Minimum Manhattan Network Problem
    (2015) Schnizler, Michael
    In this thesis we consider the Generalized Minimum Manhattan Network Problem: given a set containing n pairs of points in R2 or Rd, the goal is to find a rectilinear network of minimal length which contains a path of minimal length (a so-called Manhattan path) between the two points of each pair. We restrict our search to a discrete subspace and show that under specific conditions an optimal solution can be found in polynomial time using a dynamic program. The conditions concern the intersection graph of the bounding boxes of the pairs. Its maximum degree as well as the treewidth must be bounded by two constants which are independent of n. Finally, we present a simple greedy algorithm for practical purposes.
  • Thumbnail Image
    ItemOpen Access
    Circuit complexity of group theoretic problems
    (2021) Weiß, Armin; Diekert, Volker (Prof. Dr. rer. nat.)
    In dieser kumulativen Habilitationsschrift werden sechs Arbeiten zum Thema "Schaltkreiskomplexität von Gruppentheoretischen Problemen" zusammengefasst. An vorderster Stelle steht hierbei das Wortproblem: Gegeben ein Wort über den Erzeugern einer Gruppe, ist die Frage, ob das Wort das Einselement der Gruppe darstellt. Daneben werden noch weitere Probleme, wie das Konjugationsproblem, das Power-Wortproblem (wie das Wortproblem, aber die Eingabe wird in komprimierter Form gegeben) und das Lösen von Gleichungen betrachtet. Die meisten der hier zusammengefassten Arbeiten betrachten die genannten Probleme für spezielle Klassen von Gruppen und klassifizieren deren Komplexität mit Methoden der Schaltkreiskomplexität. Eine Ausnahme bildet die letzte Arbeit zum Thema Gleichungen: hier liegt der Zusammenhang zur Schaltkreiskomplexität darin, dass sich das Erfüllbarkeitsproblem für Gleichungen in endlichen auslösbaren Gruppen ähnlich verhält wie das Erfüllbarkeitsproblem für CC^0 Schaltkreise.
  • Thumbnail Image
    ItemOpen Access
    Equation satisfiability in solvable groups
    (2022) Idziak, Paweł; Kawałek, Piotr; Krzaczkowski, Jacek; Weiß, Armin
    The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. 178 (1), 253-262, 10 ) where they showed that this problem is in P for nilpotent groups while it is NP -complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor G / H . This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.