We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

The Complexity of Some Geometric Proof Systems

GHANI, ABDUL,AZIZ,SAUD,ABDUL (2023) The Complexity of Some Geometric Proof Systems. Doctoral thesis, Durham University.



In this Thesis we investigate proof systems based on Integer Linear Programming. These methods inspect the solution space of an unsatisfiable propositional formula and prove that this space contains no integral points.

We begin by proving some size and depth lower bounds for a recent proof system, Stabbing Planes, and along the way introduce some novel methods for doing so.

We then turn to the complexity of propositional contradictions generated uniformly from first order sentences, in Stabbing Planes and Sum-Of-Squares.

We finish by investigating the complexity-theoretic impact of the choice of method of generating these propositional contradictions in Sherali-Adams.

Item Type:Thesis (Doctoral)
Award:Doctor of Philosophy
Keywords:Proof Complexity, Integer Linear Programming
Faculty and Department:Faculty of Science > Computer Science, Department of
Thesis Date:2023
Copyright:Copyright of this thesis is held by the author
Deposited On:17 Feb 2023 09:25

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter