| 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.
|
|
| 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.
|
  | | | | | | | | | | | | | | | | | | | Jun
11 | 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 | Apr
13 |
| Monat | Jun
11 | 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 | Apr
13 | | Startseite | 2 | 4 | | 5 | | 2 | 1 | | | | 3 | 6 | 2 | | | | | | 2 | | PDF | 5 | 4 | 2 | 6 | 4 | 5 | 2 | 8 | 6 | 7 | 3 | 12 | 6 | 7 | 9 | 9 | 4 | 19 | 7 |
Gesamtzahl der Zugriffe seit Jun 2011: - Startseite – 27 (1.42 pro Monat)
- PDF – 125 (6.58 pro Monat)
|
