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 7 of 7 for “"Proof Complexity"”.
-
Rank Lower Bounds in Propositional Proof Systems Based on Integer Linear Programming Methods
The work of this thesis is in the area of proof complexity, an area which looks to uncover the limitations of proof systems. In this thesis we investigate the rank complexity of tautologies for several of the most important proof systems based on integer linear programming methods. The three main …
-
Resolution Complexity of Random Constraint Satisfaction Problems
The resolution complexity of random constraint satisfaction problems is a widely studied topic. This line of research started with a seminal paper by Chvátal and Szemeréd. They showed that for any 𝑘 ≥ 3, w.h.p. an unsatisfiable random 𝑘-SAT instance has exponentially high resolution complexity when …
-
Propositional proof systems : efficiency and automatizability
… two fundamental questions in propositional proof complexity: lower bounds on the size of the shortest proof and automatizability of propositional proof systems. With respect to the first part, we develop a new paradigm for proving lower bounds in propositional calculus. Our method is based …
-
Polynomial ideals in algebraic complexity
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms
-
Red-blue and standard pebble games : complexity and applications in the sequential and parallel models
… compilers, and, more recently, propositional proof complexity and memory-hard functions. Much previous research has been done in analyzing the computational complexity of the standard pebble game in a variety of settings. It has been shown previously that computing an optimal strategy using …
-
TRACTABLE DEPTH-BOUNDED APPROXIMATIONS TO SOME PROPOSITIONAL LOGICS. TOWARDS MORE REALISTIC MODELS OF LOGICAL AGENTS.
… structural rule(s), can be used as a direct-proof and a refutation method, and is interesting independently of the approach in that it has an exponential speed-up on its tableau system counterpart. The latter given that we introduce a new class of examples which we prove to be hard for all …