Regular resolution lower bounds for the weak pigeonhole principle
From MaRDI portal
(Redirected from Publication:558246)
The paper is devoted to the study of the complexity of resolution proofs of the weak pigeonhole principle WPHP. It is shown that for any \(m\), any regular resolution proof for WPHP\(^{m}_{n}\) (i.e., weak pigeonhole principle with \(m\) pigeons and \(n\) holes) is of length \(\Omega (2^{n^{\epsilon}})\), where \(\epsilon > 0\) is some global constant.
Recommendations
Cited in
(12)- Resolution lower bounds for the weak functional pigeonhole principle.
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Width versus size in resolution proofs
- On the weak pigeonhole principle
- scientific article; zbMATH DE number 1223618 (Why is no real title available?)
- scientific article; zbMATH DE number 1789924 (Why is no real title available?)
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- Regular resolution lower bounds for the weak pigeonhole principle
- Approximate Euler characteristic, dimension, and weak pigeonhole principles
- Resolution lower bounds for the weak pigeonhole principle
- Propositional proof complexity
- Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
This page was built for publication: Regular resolution lower bounds for the weak pigeonhole principle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558246)
