Show simple item record

2006-08-31Dissertation DOI: 10.18452/15520
Disjoint NP-pairs and propositional proof systems
dc.contributor.authorBeyersdorff, Olaf
dc.date.accessioned2017-06-18T07:49:05Z
dc.date.available2017-06-18T07:49:05Z
dc.date.created2006-09-01
dc.date.issued2006-08-31
dc.identifier.urihttp://edoc.hu-berlin.de/18452/16172
dc.description.abstractDie Theorie disjunkter NP-Paare, die auf natürliche Weise statt einzelner Sprachen Paare von NP-Mengen zum Objekt ihres Studiums macht, ist vor allem wegen ihrer Anwendungen in der Kryptografie und Beweistheorie interessant. Im Zentrum dieser Dissertation steht die Analyse der Beziehung zwischen disjunkten NP-Paaren und aussagenlogischen Beweissystemen. Haben die Anwendungen der NP-Paare in der Beweistheorie maßgeblich das Verständnis aussagenlogischer Beweissysteme gefördert, so beschreiten wir in dieser Arbeit gewissermaßen den umgekehrten Weg, indem wir Methoden der Beweistheorie zur genaueren Untersuchung des Verbands disjunkter NP-Paare heranziehen. Insbesondere ordnen wir jedem Beweissystem P eine Klasse DNPP(P) von NP-Paaren zu, deren Disjunktheit in dem Beweissystem P mit polynomiell langen Beweisen gezeigt werden kann. Zu diesen Klassen DNPP(P) zeigen wir eine Reihe von Resultaten, die illustrieren, dass robust definierten Beweissystemen sinnvolle Komplexitätsklassen DNPP(P) entsprechen. Als wichtiges Hilfsmittel zur Untersuchung aussagenlogischer Beweissysteme und der daraus abgeleiteten Klassen von NP-Paaren benutzen wir die Korrespondenz starker Beweissysteme zu erststufigen arithmetischen Theorien, die gemeinhin unter dem Schlagwort beschränkte Arithmetik zusammengefasst werden. In der Praxis trifft man statt auf zwei häufig auf eine größere Zahl konkurrierender Bedingungen. Daher widmen wir uns der Erweiterung der Theorie disjunkter NP-Paare auf disjunkte Tupel von NP-Mengen. Unser Hauptergebnis in diesem Bereich besteht in der Charakterisierung der Fragen nach der Existenz optimaler Beweissysteme und vollständiger NP-Paare mit Hilfe disjunkter Tupel.ger
dc.description.abstractDisjoint NP-pairs are an interesting complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this dissertation we explore the connection between disjoint NP-pairs and propositional proof complexity. This connection is fruitful for both fields. Various disjoint NP-pairs have been associated with propositional proof systems which characterize important properties of these systems, yielding applications to areas such as automated theorem proving. Further, conditional and unconditional lower bounds for the separation of disjoint NP-pairs can be translated to results on lower bounds to the length of propositional proofs. In this way disjoint NP-pairs have substantially contributed to the understanding of propositional proof systems. Conversely, this dissertation aims to transfer proof-theoretic knowledge to the theory of NP-pairs to gain a more detailed understanding of the structure of the class of disjoint NP-pairs and in particular of the NP-pairs defined from propositional proof systems. For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard or complete for DNPP(P). Moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist. As an important tool for our investigation we use the connection of propositional proof systems and disjoint NP-pairs to theories of bounded arithmetic.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectdisjunkte NP-Paareger
dc.subjectaussagenlogische Beweissystemeger
dc.subjectbeschränkte Arithmetikger
dc.subjectKomplexitätstheorieger
dc.subjectdisjoint NP-pairseng
dc.subjectpropositional proof systemseng
dc.subjectbounded arithmeticeng
dc.subjectcomplexity theoryeng
dc.subject.ddc004 Informatik
dc.titleDisjoint NP-pairs and propositional proof systems
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-10067498
dc.identifier.doihttp://dx.doi.org/10.18452/15520
dc.identifier.alephidHU001816254
dc.date.accepted2006-07-22
dc.contributor.refereeKöbler, Johannes
dc.contributor.refereeGrohe, Martin
dc.contributor.refereePudlak, Pavel
dc.subject.dnb28 Informatik, Datenverarbeitung
local.edoc.type-nameDissertation
local.edoc.institutionMathematisch-Naturwissenschaftliche Fakultät II

Show simple item record