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"”.

  1. Properties of oracle classes that collapse or separate complexity classes

    oxford Restricted access

  2. 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 …

    wurz-thes Repository record for Structural Properties of NP-Hard Sets and Uniform Characterisations of Complexity Classes (opens in a new tab)

  3. 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 …

    oxford Repository record for Structural results for total search complexity classes with applications to game theory and optimisation (opens in a new tab)

  4. 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 …

    unt Repository record for On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes (opens in a new tab)

  5. 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 …

    toronto-retro Repository record for Uniformity and Nonuniformity in Proof Complexity (opens in a new tab)

  6. 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 …

    iastate Repository record for Fractals in complexity and geometry (opens in a new tab)

  7. 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 …

    wurz-thes Repository record for Multiobjective Traveling Salesman Problems and Redundancy of Complete Sets (opens in a new tab)

  8. 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.

    waterloo Repository record for Lower Bounds and Derandomization (opens in a new tab)

  9. 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 …

    wurz-thes Repository record for Generalized Satisfiability Problems (opens in a new tab)

  10. 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.

    wurz-thes Repository record for Algebraic closures in complexity theory (opens in a new tab)

  11. 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 …

    wurz-thes Repository record for Operators of Higher Order (opens in a new tab)

  12. 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. …

    texas Repository record for Computational applications of invariance principles (opens in a new tab)

  13. 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 …

    iastate Repository record for Relations between Space-Bounded and Adaptive Massively Parallel Computations (opens in a new tab)

  14. Ανάλυση πολυπλοκότητας αεροπορικών αποστολών και επιδράσεις στην ασφάλεια και στην επιχειρησιακή απόδοση

    … 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 …

    greece Repository record for Ανάλυση πολυπλοκότητας αεροπορικών αποστολών και επιδράσεις στην ασφάλεια και στην επιχειρησιακή απόδοση (opens in a new tab)

  15. 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 …

    bu Repository record for Parallelism with limited nondeterminism (opens in a new tab)

  16. 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 …

    nus Repository record for AUTOMATIC REGISTER MACHINE: A COMPUTATION MODEL WITH AUTOMATIC FUNCTIONS AND RELATIONS AS ITS OPERATIONS (opens in a new tab) Download file for AUTOMATIC REGISTER MACHINE: A COMPUTATION MODEL WITH AUTOMATIC FUNCTIONS AND RELATIONS AS ITS OPERATIONS (opens in a new tab)

  17. 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 …

    uno Repository record for A Theory of Preimage Complexity: Data-structures, Complexity Measures and Applications to Endofunctions and Associated Digraphs (opens in a new tab)

  18. 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 …

    wurz-thes Repository record for The complexity of membership problems for finite recurrent systems and minimal triangulations (opens in a new tab)

Page 1 of 3