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 102 for “"PSPACE"”.
-
Evaluating conjunctive and graph queries over the EL profile of OWL 2
… in OWL 2 EL and show that the problem is PSpace-complete in combined complexity, the complexity measured in the total size of the input. All the previously known approaches encode the regular role inclusions using finite automata that can be worst-case exponential in size, and thus are not …
-
Empirical Research into the Intractability of Finite State Machines
… has established that State Verification is a PSPACE-complete problem, but the proof did not provide an empirical verification. A primary objective of this research is to provide the empirical evidence to support the theoretic proof that the State Verification problem is PSPACE-complete. A …
-
Relations between Space-Bounded and Adaptive Massively Parallel Computations
… We establish that it is unlikely that $\PSPACE$ admits $\AMPC$ algorithms, even with polynomially many rounds. We also establish that showing $\PSPACE$ is a subclass of (nonuniform) $\AMPC$ with polynomially many rounds leads to a significant separation result in complexity theory, namely …
-
Algorithmic randomness and analysis
… space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation …
-
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
… and that SATQBF is a complete problem for PSPACE. As the expressibility of SO is known to equal the class PH, then we know that there must be an SO formula which can express SATQBFk. On the other hand, PSPACE is known to be equal in expressive power to SO with the addition of a second order …
-
On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set
… problems, this problem has been shown to be PSPACE-complete, while for some problems in P, this problem could be either in P or PSPACE-complete. However, knowing the complexity of a decision problem does not directly imply the complexity of its st-connectivity problem. Therefore, it is …
-
Kolmogorov extraction and resource-bounded zero-one laws
… Our results include: (i) If Dim[subscript pspace](E)> 0, then Dim[subscript pspace](E/O(l)) = 1. (ii) Dim(E/O(l) l ESPACE) is either 0 or 1. (iii) Dim(E/poly l ESPACE) is either 0 or 1. (iv) Either Dim[superscript (1) over subscript psspace](E/O(n)) = 0 or Dim[superscript ( -1) over …
-
Complexity cores in average-case complexity theory
… exist for complexity classes such as EXP and PSPACE.</p> <p>This worst-case to average-case connections for classes such as EXP and</p> <p>PSPACE are obtained via random self-reductions. There is evidence that</p> <p>techniques used to obtain worst-case to average-case connections for EXP …
-
Automata Linear Dynamic Logic on Finite Traces
… First-Order Logic and satisfiability for LTL is PSPACE-complete. Linear Dynamic Logic (LDL), another temporal logic, is equivalent to Monadic Second-Order Logic, but its method of satisfiability checking cannot be applied to a nontrivial subset of LDL formulas. In this thesis I introduce Automata …
-
To and Fro Between Tableaus and Automata for Description Logics
… fuer Implementierungen und fuer den Nachweis von PSPACE- und NEXPTIME-Resultaten, waehrend Automaten sich besonders fuer EXPTIME-Resultate anbieten. Zudem ermoeglichen sie eine vom Standpunkt der Theorie aus elegantere Handhabung von unendlichen Strukturen, eignen sich aber wesentlich schlechter …
-
Computing Winning Strategies for Poset Games
… winning strategies for the game of Chomp is in PSPACE. \Ne also present the idea of "Game Completeness", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W<sup>1</sup><sub>1</sub> can …
-
A study of one-turn quantum refereed games
… the best known upper bound on QRG(1) was PSPACE. We have proved that if one of the provers is completely classical, sending a classical probability distribution instead of a quantum state, the new class, which we name CQRG(1), is contained in Ǝ · PP (non- deterministic polynomial-time …
-
Solving moving-blocks problems
… of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we …
-
On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes
… famously in 1992 with the 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 …
-
Applications of Games to Propositional Proof Complexity
… as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as …
-
Proof Complexity for Quantified Boolean Formulas
… Deciding whether a QBF is true or false is PSPACE-complete and a wide range of mathematical and industrial problems can be expressed as QBFs. QBF proof complexity is the theoretical analysis of algorithmic techniques for solving QBFs. We make a detailed comparison of the proof systems Q-Res, …
-
Inkrementální induktivní pokrytelnost pro alternující konečné automaty
… Aj keď je známe, že problém je sám o sebe PSpace-ťažký, zameriavame sa na to, aby bolo rozhodovanie prázdnosti výpočetne prijateľné v niektorých triedach automatov s praktickým využitím. Dosiahli sme niekoľko zaujímavýcch výsledkov v porovnaní so špičkovými algoritmami, predovšetkým v …
-
Locality and Complexity in Quantum Information Dynamics
… not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum …
-
Exploiting Problem Structure in QBF Solving
… Quantified Boolean Formula (QBF) is a canonical PSPACE-complete problem. It provides a powerful framework for encoding problems that lie in PSPACE. These include many problems in automatic verification, and problems with discrete uncertainty or non-determinism. Two person adversarial games are …
-
Distance Desert Automata and Star Height Substitutions
… of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n2) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, …
Page 1 of 6