With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
Dissertation/Thesis Abstract
-
Other Available Formats:
-
Full Text - PDF
(912.11 KB)
This thesis on propositional proof systems and disjoint NP-pairs gives a survey of these fields. We present history and motivation of both theories by giving examples for their use. The reader is then introduced into the formal notions of the fields. Dedicated chapters present important and outstanding results from the theories. Some results are proven, some results are given without a proof. It follows a chapter that presents the relation of both fields with a result due to Razborov. As for none of the assertions in this thesis the absolute truth value is known, we also survey some oracles relative to which we know the truth value of important statements. We finally look into open questions and suggest future work on both fields.
| Advisor: | Selman, Alan L. |
| Commitee: | Regan, Kenneth W. |
| School: | State University of New York at Buffalo |
| Department: | Computer Science and Engineering |
| School Location: | United States -- New York |
| Source: | MAI 53/06M(E), Masters Abstracts International |
| Source Type: | DISSERTATION |
| Subjects: | Computer science |
| Keywords: | Disjoint np-pairs, ESY-conjectures, Propositional proof systems |
| Publication Number: | 1567056 |
| ISBN: | 978-1-321-26607-8 |
