Why are proof complexity lower bounds hard?
We formalize and study the question of whether there are inherent difficulties to showing lower bounds on propositional proof complexity. We establish the following unconditional result: Propositional proof systems cannot efficiently show that truth tables of random Boolean functions lack polynomial...
| Principais autores: | , |
|---|---|
| Formato: | Conference item |
| Publicado em: |
Institute of Electrical and Electronics Engineers
2020
|