
Non-classical Aspects in Proof Complexity
Cuvillier Verlag eBooks
Published on 9. March 2012
140 pages
978-3-7369-4036-9 (ISBN)
System requirements
for PDF without DRM
E-Book Single Licence
You are acquiring a single user licence for this eBook, which you might not transfer. [L]
Available for download
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
Proof complexity focuses on the complexity of theorem proving procedures, a
topic which is tightly linked to questions from computational complexity (the
separation of complexity classes), first-order arithmetic theories (bounded arithmetic),
and practical questions as automated theorem proving. One fascinating
question in proof complexity is whether powerful computational resources as randomness
or oracle access can shorten proofs or speed up proof search. In this
dissertation we investigated these questions for proof systems that use a limited
amount of non-uniform information (advice). This model is very interesting as---
in contrast to the classical setting---it admits an optimal proof system as recently
shown by Cook and Krajícek. We give a complete complexity-theoretic classification
of all languages admitting polynomially bounded proof systems with advice
and explore whether the advice can be simplified or even eliminated while still
preserving the power of the system.
Propositional proof systems enjoy a close connection to bounded arithmetic.
Cook and Krajícek (JSL'07) use the correspondence between proof systems with
advice and arithmetic theories to obtain a very strong Karp-Lipton collapse result
in bounded arithmetic: if SAT has polynomial-size Boolean circuits, then the
polynomial hierarchy collapses to the Boolean hierarchy. Here we show that this
collapse consequence is in fact optimal with respect to the theory PV, thereby
answering a question of Cook and Krajícek.
The second main topic of this dissertation is parameterized proof complexity, a
paradigm developed by Dantchev, Martin, and Szeider (FOCS'07) which transfers
the highly successful approach of parameterized complexity to the study of proof
lengths. In this thesis we introduce a powerful two player game to model and
study the complexity of proofs in a tree-like Resolution system in a setting arising
from parameterized complexity. This game is also applicable to show strong
lower bounds in other tree-like proof systems. Moreover, we obtain the first lower
bound to the general dag-like Parameterized Resolution system for the pigeonhole
principle and study a variant of the DPLL algorithm in the parameterized setting.
More details
Language
English
Place of publication
Göttingen
Germany
File size
0,79 MB
ISBN-13
978-3-7369-4036-9 (9783736940369)
Schweitzer Classification
Other editions
Additional editions

Olaf Beyersdorff
Non-classical Aspects in Proof Complexity
Book
03/2012
1st Edition
Cuvillier Verlag
€19.95
Shipment within 15-20 days
Person
Author/originator
Content
- Intro
- Zusammenfassung
- Contents
- Acknowledgments
- Chapter 1Introduction
- Chapter 2Proof Complexity
- Chapter 3Notions from ComputationalComplexity
- Chapter 4Proof Systems that Take Advice
- Chapter 5Proof Systems with Advice andBounded Arithmetic
- Chapter 6Prover-Delayer Games
- Chapter 7ParameterizedPro of Complexity
- Chapter 8The Broader Picture
- Bibliography
- Index
System requirements
File format: PDF
Copy protection: without DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook does not use copy protection or Digital Rights Management.
For more information, see our eBook Help page.