English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this dissertation, we will investigate lower bounds on the complexity of variousproblems. Depending on what kind of computational resource the term "complexity" refers to, estab¬ lishing a lower bound, typically expressed asymptotically in some parameter, means to prove that a given task can only be solvedif we are given as many computationalresources as the lower bound indicates. Usually, the most valuable computationalresource is time, and hence, complexity theory revolves around the idea of lower-bounding the amount of time necessary to solve a, computationalproblem, e. g., an optimization problem. Depending on the chosen mode of computation, this quantity will vary. Nondeterministic computations(i. e., randomized computations, with an arbitrarilysmall chanceof success), like approximationalgorithms (i. e., we put up with a feasible Solution to an optimization problem which is not optimal, but only close to optimal), are generally believed to be strictly more powerful than deterministic exact computations. While for practical purposes, it is safe to make this assumption, theoretical research focuses on what, precisely, might constitutethis alleged power of nondeterminism. Accordingly, this dissertation is subdivided into two parts. Part I deals with the theoretical question of separatingclasses of finite automa,ta of different '"amounts"of nondeterminism, where the amount of nondeterminism is measured by means of the ambiguity of an automaton. It is a longstanding open problem whether there are regulärlanguages such that automata of constant ambiguitywould need to contain substantially more states than automata of polynomialambiguityto recognizethem. Here, we will outline a new approach to proving the existence of such a gap, including a new technique to lowcr-bound the number of states of constantly ambiguous automata. This discussion will involve weighted finite automata, and we will also have a look at their applicationin signal processing and how binary Operations on digital signals represented by finite automata can and cannot, respectively, be evaluated. Our goal in Part II is to investigate the approximability of some generalizations of TSP. The most importantof these generalizations is TSP with time Windows, where for each vertexof the input graph, an openingand a closing point of time for a window is given, and the respective vertex must be visited while the window is open. This generalizedproblem naturallyand frequentlyappears in a numberof applications, the most prominentof which may be verfiele routing. By combining methods from the field of approximationalgorithms with ideas from the theory of parameterized complexity, we obtain the concept of parameterized approxima¬ tion, using which we devise tractable algorithms for some of our TSP generalizations.

Descriptional and computational complexity in relation to the practicability of computation and computational modes