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...
Հիմնական հեղինակներ: | Pich, J, Santhanam, R |
---|---|
Ձևաչափ: | Conference item |
Հրապարակվել է: |
Institute of Electrical and Electronics Engineers
2020
|
Նմանատիպ նյութեր
-
Hardness magnification near state-of-the-art lower bounds
: Oliveira, I, և այլն
Հրապարակվել է: (2019) -
Hardness magnification near state-of-the-art lower bounds
: Oliveira, IC, և այլն
Հրապարակվել է: (2021) -
Iterated lower bound formulas: a diagonalization-based approach to lower bounds in proof complexity
: Santhanam, R, և այլն
Հրապարակվել է: (2021) -
Beyond natural proofs: Hardness magnification and locality
: Chen, L, և այլն
Հրապարակվել է: (2020) -
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
: Pich, J, և այլն
Հրապարակվել է: (2021)