Pages that link to "Item:Q1854546"
From MaRDI portal
The following pages link to Lower bounds for the weak pigeonhole principle and random formulas beyond resolution (Q1854546):
Displaying 15 items.
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs (Q430840) (← links)
- Mean-payoff games and propositional proofs (Q716324) (← links)
- Short propositional refutations for dense random 3CNF formulas (Q741088) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- On the automatizability of resolution and related propositional proof systems (Q1881219) (← links)
- On the complexity of resolution with bounded conjunctions (Q1885907) (← links)
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
- Separation results for the size of constant-depth propositional proofs (Q2566064) (← links)
- On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution (Q3012839) (← links)
- The polynomial and linear hierarchies in models where the weak pigeonhole principle fails (Q3503756) (← links)
- Resolution and the binary encoding of combinatorial principles (Q5091756) (← links)
- Approximate Euler characteristic, dimension, and weak pigeonhole principles (Q5311719) (← links)
- The Complexity of Propositional Proofs (Q5444711) (← links)
- LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE (Q5501765) (← links)
- Proof complexity and the binary encoding of combinatorial principles (Q6562831) (← links)
