Pages that link to "Item:Q4292593"
From MaRDI portal
The following pages link to Lower bounds to the size of constant-depth propositional proofs (Q4292593):
Displayed 33 items.
- The limits of tractability in resolution-based propositional proof systems (Q408157) (← links)
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Lifting lower bounds for tree-like proofs (Q475337) (← links)
- A note on propositional proof complexity of some Ramsey-type statements (Q627444) (← links)
- On the elimination of quantifier-free cuts (Q650922) (← links)
- Short propositional refutations for dense random 3CNF formulas (Q741088) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- On the complexity of cutting-plane proofs using split cuts (Q969513) (← links)
- A proper hierarchy of propositional sequent calculi (Q1350509) (← links)
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (Q1377580) (← links)
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF (Q1383164) (← links)
- Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II (Q1575637) (← links)
- Relative efficiency of propositional proof systems: Resolution vs. cut-free LK (Q1577476) (← links)
- On the complexity of resolution with bounded conjunctions (Q1885907) (← links)
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies (Q2500481) (← links)
- How many times do we need an assumption to prove a tautology in minimal logic? Examples on the compression power of classical reasoning (Q2520659) (← links)
- Separation results for the size of constant-depth propositional proofs (Q2566064) (← links)
- Tautologies from Pseudo-Random Generators (Q2736584) (← links)
- Satisfiability via Smooth Pictures (Q2817998) (← links)
- Proofs with monotone cuts (Q2888631) (← links)
- FRAGMENTS OF APPROXIMATE COUNTING (Q2921008) (← links)
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems (Q2944868) (← links)
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← links)
- Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds (Q3012837) (← links)
- Examining Fragments of the Quantified Propositional Calculus (Q3617380) (← links)
- Some applications of propositional logic to cellular automata (Q3650319) (← links)
- Lower bounds for cutting planes proofs with small coefficients (Q4372903) (← links)
- Lower bounds for resolution and cutting plane proofs and monotone computations (Q4372917) (← links)
- NP search problems in low fragments of bounded arithmetic (Q5294030) (← links)
- An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams (Q5387310) (← links)
- The Complexity of Propositional Proofs (Q5444711) (← links)
- A new proof of the weak pigeonhole principle (Q5894824) (← links)
- Proof Complexity of Non-classical Logics (Q5894972) (← links)