05 Fakultät Informatik, Elektrotechnik und Informationstechnik

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

Browse

Subject: search.filters.subject.004End date: 2022Author: search.filters.author.Weiß, ArminPublication Type: search.filters.UBSTyp.Zeitschriftenartikel

Search Results

Now showing 1 - 2 of 2
  • 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.
  • Thumbnail Image
    ItemOpen Access
    On the average case of MergeInsertion
    (2020) Stober, Florian; Weiß, Armin
    MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of nlogn-1.4005n+o(n) comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for n up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to Manacher’s combination of merging and MergeInsertion as well as to the recent combined algorithm with (1,2)-Insertionsort by Iwama and Teruyama.