Binarisation via Dualisation for Valued Constraints
Authors: David Cohen, Martin Cooper, Peter Jeavons, Stanislav Zivny
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The complexity of constraint satisfaction for various forms of constraints has been widely-studied, both to inform the choice of appropriate algorithms, and to understand better the boundary between polynomial-time complexity and NP-hardness. Here we show that this transformation, although it changes the domain of the constraints, preserves all the relevant algebraic properties that determine the complexity. Moreover, we show that the dual encoding preserves many of the key algorithmic properties of the original instance. Hence, we obtain a simple proof of the fact that to classify the computational complexity of all valued constraint languages it suffices to classify only binary valued constraint languages. |
| Researcher Affiliation | Academia | David A. Cohen Royal Holloway University of London dave@cs.rhul.ac.uk Martin C. Cooper IRIT University of Toulouse III cooper@irit.fr Peter G. Jeavons, Stanislav ˇZivn y University of Oxford {peter.jeavons,standa.zivny} @cs.ox.ac.uk |
| Pseudocode | No | The paper describes algorithms and transformations in text and definitions but does not provide pseudocode blocks. |
| Open Source Code | No | The paper does not contain any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving dataset training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving dataset validation. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, therefore, it does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software with version numbers used for running experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup or hyperparameters for empirical evaluation. |