edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Olaf Beyersdorff
Titel: Disjoint NP-pairs and propositional proof systems
Gutachter: Johannes Köbler; Martin Grohe; Pavel Pudlak
Erscheinungsdatum: 31.08.2006
Volltext: pdf (urn:nbn:de:kobv:11-10067498)
Fachgebiet(e): Informatik
Schlagwörter (ger): disjunkte NP-Paare, aussagenlogische Beweissysteme, beschränkte Arithmetik, Komplexitätstheorie
Schlagwörter (eng): disjoint NP-pairs, propositional proof systems, bounded arithmetic, complexity theory
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Beyersdorff, Olaf: Disjoint NP-pairs and propositional proof systems; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 31.08.2006, urn:nbn:de:kobv:11-10067498
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Die 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.
Abstract (eng):
Disjoint 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.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 4 Zugriffe PDF: 4 Zugriffe PDF: 2 Zugriffe Startseite: 5 Zugriffe PDF: 6 Zugriffe PDF: 4 Zugriffe Startseite: 2 Zugriffe PDF: 5 Zugriffe Startseite: 1 Zugriffe PDF: 2 Zugriffe PDF: 8 Zugriffe PDF: 6 Zugriffe PDF: 7 Zugriffe Startseite: 3 Zugriffe PDF: 3 Zugriffe Startseite: 6 Zugriffe PDF: 12 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe PDF: 7 Zugriffe PDF: 9 Zugriffe PDF: 9 Zugriffe PDF: 4 Zugriffe PDF: 19 Zugriffe PDF: 13 Zugriffe Startseite: 1 Zugriffe PDF: 11 Zugriffe Startseite: 2 Zugriffe PDF: 7 Zugriffe PDF: 19 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe PDF: 12 Zugriffe Startseite: 1 Zugriffe PDF: 17 Zugriffe Startseite: 5 Zugriffe PDF: 22 Zugriffe PDF: 17 Zugriffe Startseite: 2 Zugriffe PDF: 18 Zugriffe Startseite: 3 Zugriffe PDF: 19 Zugriffe Startseite: 1 Zugriffe PDF: 26 Zugriffe Startseite: 2 Zugriffe PDF: 20 Zugriffe PDF: 35 Zugriffe PDF: 48 Zugriffe Startseite: 2 Zugriffe PDF: 41 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Startseite 4   5   2 1       3 6 2             1 2   2 2   1 5   2 3 1 2     2
PDF 4 2 6 4 5 2 8 6 7 3 12 6 7 9 9 4 19 13 11 7 19 10 10 12 17 22 17 18 19 26 20 35 48 41

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 46 (1.35 pro Monat)
  • PDF – 458 (13.47 pro Monat)
 
 
Generiert am 30.07.2014, 13:48:52