scientific article; zbMATH DE number 1424047

zbMATH Open0942.03010MaRDI QIDQ4945238FDOQ4945238

Authors: Jacobo Torán 

Publication date: 23 August 2000

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 1304340
• Space bounds for resolution
• Resolvability of spaces having small spread or extent
• Size-space tradeoffs for resolution
• Maximally resolvable lower density spaces
• Towards an optimal separation of space and length in resolution
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• scientific article
• Lower space bounds for randomized computation
• Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space

zbMATH Keywords

lower boundsTseitin formulascomplexity measureresolution refutationpebble gameresolution spacePigeonhole Principle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (7)

• A simplified way of proving trade-off results for resolution
• Reversible pebble games and the relation between tree-like and general resolution space
• A combinatorial characterization of resolution width
• Title not available (Why is that?)
• Space complexity of random formulae in resolution
• An Upper Bound on the Space Complexity of Random Formulae in Resolution
• Space bounds for resolution

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 Q4945238)