Evaluating logic gate constraints in local search for structured satisfiability problems

Der Artikel "Evaluating logic gate constraints in local search for structured satisfiability problems" untersucht die Verwendung von logic gate constraints in lokalen Suchalgorithmen für strukturierte Zufriedenheitsprobleme. Sie konzentriert sich auf das Problem der Propositional Satisfiability (SAT), das sowohl in der Wissenschaft als auch in der Industrie von entscheidender Bedeutung ist. Der Artikel diskutiert die Erkennung von Logikgattern aus Klausalmustern in Konjunktiven Normalformeln (CNF) und ihre Auswirkungen auf lokale Suchalgorithmen. Es unterstreicht die Bedeutung bestimmter Tore wie xor, xnor, eq und nicht bei der Verbesserung der Leistung dieser Algorithmen. Die Arbeit erweitert frühere Forschungen von Pham et al., liefert eine detaillierte Beschreibung des Solver-Systems und führt umfangreiche Experimente an Benchmark-Instanzen aus SATLib und SAT-Wettbewerben durch. Die Autoren bewerten auch die Leistung verschiedener lokaler Suchalgorithmen, darunter AdaptNovelty + und CCAnr, die an die Bewältigung von Logikgatterrestriktionen angepasst sind. Der Artikel schließt mit der Identifizierung der Logikgatter, die zur Leistungssteigerung lokaler Suchalgorithmen beitragen. Diese Arbeit ist bedeutsam, da sie ein tieferes Verständnis dafür vermittelt, wie Logikgatter in lokalen Suchalgorithmen effektiv für strukturierte Zufriedenheitsprobleme genutzt werden können.