Regular resolution lower bounds for the weak pigeonhole principle
From MaRDI portal
Publication:5175989
DOI10.1145/380752.380821zbMath1323.03090MaRDI QIDQ5175989
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/380752.380821
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
A new proof of the weak pigeonhole principle, The NP-hardness of finding a directed acyclic graph for regular resolution, Resolution lower bounds for the weak functional pigeonhole principle., Lower bounds for the weak pigeonhole principle and random formulas beyond resolution, Resolution lower bounds for perfect matching principles, Mutilated chessboard problem is exponentially hard for resolution, Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Cites Work