COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Disjoint NP-Pairs and Propositional Proof Systems
by Wisiol, Nils, M.S., State University of New York at Buffalo, 2014, 28; 1567056
Abstract (Summary)

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.

Indexing (document details)
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
Subjects: Computer science
Keywords: Disjoint np-pairs, ESY-conjectures, Propositional proof systems
Publication Number: 1567056
ISBN: 978-1-321-26607-8
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy