Space bounds for resolution

DOI10.1006/INCO.2001.2921zbMATH Open1005.03009OpenAlexW2071347463MaRDI QIDQ1854472FDOQ1854472

Authors: Juan Luis Esteban, Jacobo Torán 

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.2921

Recommendations

• scientific article; zbMATH DE number 1304340
• On space and depth in resolution
• scientific article; zbMATH DE number 1424047
• Narrow proofs may be spacious: separating space and width in resolution
• From small space to small width in resolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Hard examples for resolution
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Many hard examples for resolution
• Title not available (Why is that?)
• Short proofs are narrow -- resolution made simple
• The intractability of resolution
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Space complexity in propositional calculus

Cited In (40)

• On the complexity of resolution with bounded conjunctions
• A combinatorial characterization of treelike resolution space
• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Title not available (Why is that?)
• The Complexity of Propositional Proofs
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
• Towards an optimal separation of space and length in resolution
• Total space in resolution is at least width squared
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• Space proof complexity for random 3-CNFs
• On semantic cutting planes with very small coefficients
• A simplified way of proving trade-off results for resolution
• Space complexity in propositional calculus
• Cumulative space in black-white pebbling and resolution
• A tutorial on time and space bounds in tree-like resolution
• A note about \(k\)-DNF resolution
• A characterization of tree-like resolution size
• Trade-offs between time and memory in a tighter model of CDCL SAT solvers
• The treewidth of proofs
• Total space in resolution
• Autonomous resolution based on DNA strand displacement
• Reversible pebble games and the relation between tree-like and general resolution space
• Cops-robber games and the resolution of Tseitin formulas
• From small space to small width in resolution
• Proofs as Games
• A combinatorial characterization of resolution width
• Space Complexity in Polynomial Calculus
• From small space to small width in resolution
• Supercritical space-width trade-offs for resolution
• The depth of resolution proofs
• Resolution-limited measure and dimension
• On space and depth in resolution
• Hard examples for resolution
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Size-space tradeoffs for resolution
• A framework for space complexity in algebraic proof systems
• Cliques enumeration and tree-like resolution proofs
• Cops-robber games and the resolution of Tseitin formulas
• Space complexity of random formulae in resolution

This page was built for publication: Space bounds for resolution

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