scientific article; zbMATH DE number 1361471

MaRDI QIDQ4699289zbMATH OpenFDO

Authors Uwe Schöning

Publication date 6 January 2002

zbMATH Keywords

expander graphsexponential lower boundKolmogorov complexitylength of resolution proof

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Hard examples for resolution
• The intractability of resolution
• Short proofs are narrow -- resolution made simple
• Short proofs are narrow—resolution made simple

Cited in

(15)

• The intractability of resolution
• Space bounds for resolution
• Resolution with counting: dag-like lower bounds and different moduli
• Unified Characterisations of Resolution Hardness Measures
• Hard examples for resolution
• Construction of expanders and superconcentrators using Kolmogorov complexity
• Expander construction in \(\mathsf{VNC}^1\)
• Graph expansion, Tseitin formulas and resolution proofs for CSP
• Tight lower bounds on the resolution complexity of perfect matching principles
• Reflections on Proof Complexity and Counting Principles
• An Introduction to Lower Bounds on Resolution Proof Systems
• On the resolution complexity of graph non-isomorphism
• scientific article; zbMATH DE number 7650367 (Why is no real title available?)
• Smaller superconcentrators of density 28
• A feasibly constructive lower bound for resolution proofs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699289)