1 option
Space in Weak Propositional Proof Systems / by Ilario Bonacina.
- Format:
- Book
- Author/Creator:
- Bonacina, Ilario, author.
- Series:
- Computer Science (Springer-11645)
- Language:
- English
- Subjects (All):
- Computers.
- Computer science--Mathematics.
- Computer science.
- Theory of Computation.
- Mathematics of Computing.
- Local Subjects:
- Theory of Computation.
- Mathematics of Computing.
- Physical Description:
- 1 online resource (XVII, 130 pages) : 15 illustrations, 8 illustrations in color
- Edition:
- First edition 2017.
- Contained In:
- Springer eBooks
- Place of Publication:
- Cham : Springer International Publishing : Imprint: Springer, 2017.
- System Details:
- text file PDF
- Summary:
- This book considers logical proof systems from the point of view of their space complexity. After an introduction to propositional proof complexity the author structures the book into three main parts. Part I contains two chapters on resolution, one containing results already known in the literature before this work and one focused on space in resolution, and the author then moves on to polynomial calculus and its space complexity with a focus on the combinatorial technique to prove monomial space lower bounds. The first chapter in Part II addresses the proof complexity and space complexity of the pigeon principles. Then there is an interlude on a new type of game, defined on bipartite graphs, essentially independent from the rest of the book, collecting some results on graph theory. Finally Part III analyzes the size of resolution proofs in connection with the Strong Exponential Time Hypothesis (SETH) in complexity theory. The book is appropriate for researchers in theoretical computer science, in particular computational complexity.
- Contents:
- Introduction
- Total Space in Resolution
- Space in Polynomial Calculus
- Space Lower Bounds: Applications
- A Postlude: SETH and Resolution Size.
- Other Format:
- Printed edition:
- ISBN:
- 978-3-319-73453-8
- 9783319734538
- Access Restriction:
- Restricted for use by site license.
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.