Upper and lower bounds on the complexity of generalised resolution and generalised constraint satisfaction problems

DOI10.1023/B:AMAI.0000012871.08577.0BMaRDI QIDQ1430293zbMATH OpenOpenAlexFDO

Authors Oliver Kullmann

Publication date 27 May 2004

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/b:amai.0000012871.08577.0b

zbMATH Keywords

constraint satisfaction problemspropositional logicsatisfiability problemautomatisation of proof systemsgeneralised input resolutiongeneralised resolutiongeneralised width restricted resolutioninduced width of constraint satisfaction problemslower bounds for resolutionpolynomial time hierarchiessystems with partial instantiationupper bounds for SAT algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Principles and Practice of Constraint Programming – CP 2003
• On a generalization of extended resolution
• The intractability of resolution
• Short proofs are narrow—resolution made simple
• The Resolution Complexity of Random Constraint Satisfaction Problems

Cited in

(7)

• On a generalization of extended resolution
• Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
• Backdoors in the Context of Learning
• Generalising and unifying SLUR and unit-refutation completeness
• Parity Games and Propositional Proofs
• Generalising unit-refutation completeness and SLUR via nested input resolution
• Present and Future of Practical SAT Solving

Describes a project that uses

Uses Software

• SATO

This page was built for publication: Upper and lower bounds on the complexity of generalised resolution and generalised constraint satisfaction problems

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