From k-SAT to k-CSP: Two Generalized Algorithms
| dc.creator | Li, Liang | |
| dc.creator | Li, Xin | |
| dc.creator | Liu, Tian | |
| dc.creator | Xu, Ke | |
| dc.date | 2008-01-21 | |
| dc.date.accessioned | 2026-07-07T08:55:37Z | |
| dc.date.available | 2026-07-07T08:55:37Z | |
| dc.description | Constraint satisfaction problems (CSPs) models many important intractable NP-hard problems such as propositional satisfiability problem (SAT). Algorithms with non-trivial upper bounds on running time for restricted SAT with bounded clause length k (k-SAT) can be classified into three styles: DPLL-like, PPSZ-like and Local Search, with local search algorithms having already been generalized to CSP with bounded constraint arity k (k-CSP). We generalize a DPLL-like algorithm in its simplest form and a PPSZ-like algorithm from k-SAT to k-CSP. As far as we know, this is the first attempt to use PPSZ-like strategy to solve k-CSP, and before little work has been focused on the DPLL-like or PPSZ-like strategies for k-CSP. | |
| dc.identifier | https://arxiv.org/abs/0801.3147 | |
| dc.identifier | http://arxiv.org/abs/0801.3147 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/146325 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Artificial Intelligence | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2 | |
| dc.title | From k-SAT to k-CSP: Two Generalized Algorithms | |
| dc.type | text |