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

DOI10.1023/B:AMAI.0000012871.08577.0BzbMATH Open1081.68032OpenAlexW2061783009MaRDI QIDQ1430293FDOQ1430293

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

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

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)

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

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)