Unified Characterisations of Resolution Hardness Measures

DOI10.1007/978-3-319-09284-3_13MaRDI QIDQ3192062zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Olaf Beyersdorff, Oliver Kullmann

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://eprints.whiterose.ac.uk/80490/1/2014_PHP.pdf

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Resolvability: A selective survey and some new results
• Uniform characterizations of non-uniform complexity measures
• Hardness Characterisations and Size-width Lower Bounds for QBF Resolution
• Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution
• scientific article; zbMATH DE number 1361471
• A combinatorial characterization of resolution width
• The complexity of resolution refinements
• Resolution and the integrality of satisfiability problems
• Hard promise problems and nonuniform complexity
• scientific article; zbMATH DE number 18529

Cited in

(5)

• A game characterisation of tree-like Q-resolution size
• A game characterisation of tree-like Q-resolution size
• Total space in resolution
• Feasible interpolation for QBF resolution calculi
• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

This page was built for publication: Unified Characterisations of Resolution Hardness Measures

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