Lokala konsekventa metoder som k-konsistens är en viktig del av specialiserade lösare för problem med begränsad tillfredsställelse. I detta dokument visar vi att förmågan att använda k-konsistensteknik på ett problem med begränsad tillfredsställelse exakt fångas upp genom att använda en särskild slutledningsregel, som vi kallar negativ-hyper-upplösning, om den vanliga direktkodningen av problemet i booleska klausuler. Vi visar också att nuvarande klausullearning SAT-solvers kommer att upptäcka i förväntad polynom tid eventuella inkonsekvens som kan härledas från en viss uppsättning klausuler med hjälp av negativ-hyper-återlösningsmedel av en fast storlek. Vi kombinerar dessa två resultat för att visa att, utan att uttryckligen vara utformade för att göra det, nuvarande klausul-learning SAT-solvers effektivt simulera k-konsistens tekniker, för alla fasta värden av k. Vi ger sedan några experimentella resultat för att visa att denna funktion gör det möjligt klausul-learning SAT-solvers att effektivt lösa vissa familjer av begränsningsproblem som är utmanande för konventionella begränsningsprogrammeringslösare.
Våra tekniker har nyligen utökats för att visa att SAT-solvers med en helt slumpmässig beslutsstrategi effektivt kan simulera lokala konsekventa tekniker för allmänna problem med begränsad tillfredsställelse REF.
Local Consistency and SAT-Solvers
{'venue': 'Journal Of Artificial Intelligence Research, Volume 43, pages 329-351, 2012', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}