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 17 of 17 for “"Descriptive complexity"”.
-
Structural techniques in descriptive complexity
In 2017, Abramsky, Dawar, and Wang published a paper which gave a comonadic characterisation of pebble games, tree-width, and k-variable logic, a key trio of related concepts in Finite Model Theory. In 2018, Abramsky and Shah expanded upon this to give an analogous comonadic characterisation of …
-
Counting below #P: Classes, problems and Descriptive Complexity
Στην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη #P. Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας, είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους …
-
On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes
… that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.
-
On structural and descriptive complexity of hard counting problems the decision version of which is easy
The complexity class #P introduced by Valiant, contains the counting versions of NP problems. We focus on #PE, the class of #P functions the decision version of which is in P. In fact, we are mostly interested in a subclass of #PE, namely TotP, which contains all self-reducible #PE functions. TotP …
-
On the descriptive complexity of satisfiability on quantified Boolean formulas : a thesis presented in partial fulfilment of the requirements for the degree of Master of Information Sciences at Massey University, Wellington, New Zealand
… the relationship between logic languages and complexity classes. Then we give formal definitions and examples for FO (First-Order), SO and HO (i≥2) (Higher-Order logic). It is known that, for every k ≥1, SATQBFk is a complete problem for the level Σ [superscript P subscript k] of PH …
-
MODEL THEORY AND COMPLEXITY THEORY
Descriptive complexity theory is a branch of complexity theory that views the hardness of a problem in terms of the complexity of expressing it in some logical formalism; among the resources considered are the number of object variables, quantifier depth, type, and alternation, sentences length …
-
Bounded-curvature motion planning amid polygonal obstacles
… guarantees and run time analysis in terms of the complexity of the desired solution (see k and λ below). In a sense, our algorithms are output sensitive, which is particularly desirable because there are no known bounds on the solution complexity amid arbitrary polygonal environments. Our first …
-
Topics on the geometry and classification of Banach lattices
… 3 and 4) presents various results on the descriptive complexity of classes of Banach lattices and determines the complexity of the lattice isomorphism and isometry equivalence relations. The focus of the third part (Chapter 5) is the construction of a lattice isometrically universal …
-
In pursuit of linear complexity in discrete and computational geometry
… meshes, and (iii) bounding the expected complexity of weighted Voronoi diagrams. While these topics are broad, here the focus is on identifying structure which implies linear (or near linear) algorithmic and descriptive complexity. The first topic we consider is in geometric optimization. …
-
Some Results for FO-definable Constraint Satisfaction Problems Described by Digraph Homomorphisms
… constraints. When studying the computational and descriptive complexity of such problems it is convenient to use the equivalent formulation, introduced by Feder and Vardi, that CSPs are homomorphism problems. In this context we ask if there exists a homomorphism to some target structure. Using …
-
Repeated stressful workplace for a group of clerical workers : complexity, content, and higher-order values of their experiences
Complexity and content of the stressful workplace, and the goals or expectations of the worker were revealed through a micro-analytic, subjective, and contextual research approach. A content analysis, based on the transactional theory of stress (Lazarus & Folkman, 1984) was used to analyse 1044 …
-
Descriptive Set Theory and Measure Theory in Locally Compact and Non-locally Compact Groups
In this thesis we study descriptive-set-theoretic and measure-theoretic properties of Polish groups, with a thematic emphasis on the contrast between groups which are locally compact and those which are not. The work is divided into three major sections. In the first, working jointly with Robert …
-
An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic
We explore the possibility of automating <i>NP</i>-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (<i>SO</i>∃) logic as representation language for decision problems. Building upon the theoretical framework …
-
On Token Movement Problems
… This thesis contributes to the computational complexity landscape for these transformation problems. For solution discovery problems where the target property is to form a matching, vertex/edge cut, or shortest path, we show that even though these properties are efficiently computable in the …
-
Gödelovo dílo a jeho význam pro informatiku a filosofii
Tato práce zkoumá dopad práce Kurta Gödela, zejména jeho vět o neúplnosti, na informatiku. První část se zabývá Gödelovými filozofickými současníky – včetně Russella, Carnapa, Wittgensteina a Tarského – a jejich vlivem na něj samotného, porovnává jeho výsledky s výsledky Alana Turinga a diskutuje …