Tractable Structures for Constraint Satisfaction with Truth TablesReportar como inadecuado

Tractable Structures for Constraint Satisfaction with Truth Tables - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 DCSIT - Department of Computer Science and Information Theory

Abstract : The way the graph structure of the constraints influences the complexity of constraint satisfaction problems CSP is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer depends also on how the constraints are represented in the input. We study this question for the truth table representation of constraints. We introduce a new hypergraph measure adaptive width and show that CSP with truth tables is polynomial-time solvable if restricted to a class of hypergraphs with bounded adaptive width. Conversely, assuming a conjecture on the complexity of binary CSP, there is no other polynomial-time solvable case.

Keywords : computational complexity constraint satisfaction treewidth adaptive width

Autor: Dániel Marx -



Documentos relacionados