Resolution lower bounds for the weak functional pigeonhole principle. (Q1401365): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: N. K. Zamov / rank | |||
Property / reviewed by | |||
Property / reviewed by: N. K. Zamov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pseudorandom Generators in Propositional Proof Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4399249 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Short proofs are narrow—resolution made simple / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5769706 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4218929 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Resolution proofs of generalized pigeonhole principles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Many hard examples for resolution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4228469 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Computing Procedure for Quantification Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The intractability of resolution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4375792 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Regular resolution lower bounds for the weak pigeonhole principle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4818823 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Resolution lower bounds for perfect matching principles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4527043 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Machine-Oriented Logic Based on the Resolution Principle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5685059 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hard examples for resolution / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:51, 6 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Resolution lower bounds for the weak functional pigeonhole principle. |
scientific article |
Statements
Resolution lower bounds for the weak functional pigeonhole principle. (English)
0 references
17 August 2003
0 references
The main result of the paper is that every resolution refutation of the functional version of the pigeonhole principle must have the size \(\exp (\Omega(n/(\log m)^2))\), where \(n\) is the number of the pigeons and \(m\) is the number of holes. This fact implies an \(\exp(\Omega(n^{1/3}))\) lower bound when the number of pigeons \(m\) is arbitrary. The paper contains an overview of some open problems.
0 references
resolution method
0 references
complexity of proofs
0 references