2017 | OriginalPaper | Chapter
Some Graph-Based Formulas
Author : Ilario Bonacina
Published in: Space in Weak Propositional Proof Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We now show some further applications of the general theorems to prove space lower bounds from Chap. 3 and Chap. 4. That is we see how to prove monomial and resolution total space lower bounds for random k-CNF formulas (Sect. 7.2), the pigeonhole principle over a bipartite graph (Sect. 7.3) and Tseitin formulas (Sect. 7.4).