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

DOI10.1023/B:AMAI.0000012871.08577.0bzbMath1081.68032OpenAlexW2061783009MaRDI QIDQ1430293

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

propositional logicsatisfiability problemconstraint satisfaction problemsautomatisation 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

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

Related Items

Generalising and Unifying SLUR and Unit-Refutation Completeness ⋮ On Davis-Putnam reductions for minimally unsatisfiable clause-sets ⋮ Parity Games and Propositional Proofs ⋮ Backdoors in the Context of Learning ⋮ Present and Future of Practical SAT Solving ⋮ Generalising unit-refutation completeness and SLUR via nested input resolution

Uses Software

• SATO

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