Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 58 for “"Complexity classes"”.
-
Structural Properties of NP-Hard Sets and Uniform Characterisations of Complexity Classes
… thesis is devoted to the study of computational complexity theory, a branch of theoretical computer science. Computational complexity theory investigates the inherent difficulty in designing efficient algorithms for computational problems. By doing so, it analyses the scalability of computational …
-
Structural results for total search complexity classes with applications to game theory and optimisation
… Nash equilibrium). In order to shed light on the complexity of these problems, researchers have attempted to classify them in various subclasses of TFNP such as PPAD, PPA, PPP, PLS, and CLS. A celebrated result in this line of research is the PPAD-completeness of NASH, yielding strong evidence …
-
On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes
… result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we suggest using largeness with …
-
Uniformity and Nonuniformity in Proof Complexity
… relations between uniform and nonuniform proof complexity and computational complexity. Nonuniform proof complexity studies the lengths of proofs in various propositional proof systems such as Frege . Uniform proof complexity studies the provability strength of bounded arithmetic theories which …
-
Fractals in complexity and geometry
… have been used by computer scientists to study complexity classes for two decades. But in computer science, the usefulness of fractal dimensions was very limited before Lutz effectivized classical Hausdorff dimension to effective dimensions in 2000. With effective dimensions, a singleton set may …
-
Multiobjective Traveling Salesman Problems and Redundancy of Complete Sets
… mitotic. For different reducibility notions and complexity classes, we analyze how redundant its complete sets are. Previous research in this field concentrates on polynomial-time computable reducibility notions. The main contribution of this part of the thesis is a systematic study of the …
-
Lower Bounds and Derandomization
A major open problem in complexity theory is to determine whether randomized complexity classes such as BPP, AM, and MA have any nontrivial derandomization. This thesis investigates the derandomization of two randomized versions of the polynomial hierarchy.
-
Generalized Satisfiability Problems
In the last 40 years, complexity theory has grown to a rich and powerful field in theoretical computer science. The main task of complexity theory is the classification of problems with respect to their consumption of resources (e.g., running time or required memory). To study the computational …
-
Algebraic closures in complexity theory
… and structures which are derived from these in complexity theory. We classify problems with Boolean circuits and Boolean constraints according to their complexity. We transfer algebraic structures to structural complexity. We use the generation problem to classify important complexity classes.
-
Operators of Higher Order
… power of quantifiers applied to well-known complexity classes. In special, we are interested in existential, universal and probabilistic bounded error quantifiers ranging over words and sets of words, i.e. oracles if we think in a Turing machine model. In addition to the standard oracle …
-
Computational applications of invariance principles
… an important role in a plethora of results in complexity theory. The current thesis aims to take this program further by drawing on a variety of fundamental tools, both classical and new, in probability theory and analytic geometry. Our research contributions broadly fall into three categories. …
-
Relations between Space-Bounded and Adaptive Massively Parallel Computations
… in constant rounds from a computational complexity theory perspective. A language $L$ is in the class $\AMPC^0$ if for every $\varepsilon \in(0,1)$, there is a deterministic AMPC algorithm running in constant rounds with a $\textup{poly}(n)$ processors, where the local memory of each …
-
Ανάλυση πολυπλοκότητας αεροπορικών αποστολών και επιδράσεις στην ασφάλεια και στην επιχειρησιακή απόδοση
… validated for the consideration of all relevant Complexity Contributing Factors (CCFs). This work aims to improve the process of risk management of missions in military aviation and allow for a more thorough examination of Complexity Contributing Factors (CCFs). After a series of structured …
-
Parallelism with limited nondeterminism
Computational complexity theory studies which computational problems can be solved with limited access to resources. The past fifty years have seen a focus on the relationship between intractable problems and efficient algorithms. However, the relationship between inherently sequential problems and …
-
AUTOMATIC REGISTER MACHINE: A COMPUTATION MODEL WITH AUTOMATIC FUNCTIONS AND RELATIONS AS ITS OPERATIONS
… speed up, thus it is comparable to fairer complexity classes in Turing Machine. We start to investigate, in particular, the deterministic and non-deterministic complexity of this model for various natural problems. We then further study the alternating complexity of the model and find some …
-
A Theory of Preimage Complexity: Data-structures, Complexity Measures and Applications to Endofunctions and Associated Digraphs
… develops a new theory of finite function complexity. This novel approach is based on the structure of preimage sets generated under repeat application of the inverse. We encode this information in our primary data-structure, an square matrix called the sigma matrix. This matrix allows us …
-
The complexity of membership problems for finite recurrent systems and minimal triangulations
The dissertation thesis studies the complexity of membership problems. Generally, membership problems consider the question whether a given object belongs to a set. Object and set are part of the input. The thesis studies the complexity of membership problems for two special kinds of sets. The …
Page 1 of 3