Iterated lower bound formulas: a diagonalization-based approach to lower bounds in proof complexity
We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally. <br> We use the approach to give an explicit sequence o...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2021
|