Encoding Constraints as Binary Constraint Networks Satisfying BTP
Authors: Ruiwei Wang
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we investigate the modelling power of a well-known tractable hybrid class generalizing BCT, i.e. the class of BCNs satisfying Broken Triangle Property (BTP) called BTP Networks (BTPNs). We show that the consistency checker of BTPN can be computed by polysize monotone circuit, thus, some global constraints cannot be encoded as polysize BTPN, such as the All Different and Linear constraints. Then our study reveals that BTPN is strictly more succinct than the DNNF constraint and all 14 ad-hoc constraints discussed in (Wang and Yap 2023), such as the context-free grammar, BCT and smart table constraints. Furthermore, we also show that BTPN is as powerful as DNNF in terms of computing various operations and queries. In addition, we prove that it is NP-hard to determine the minimum sized BTPN encoding a constraint. |
| Researcher Affiliation | Academia | Ruiwei Wang School of Computing, National University of Singapore wangruiwei@u.nus.edu |
| Pseudocode | No | The paper describes algorithms and logical steps through prose and mathematical formulations (e.g., proofs for lemmas and theorems) but does not include any explicitly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not contain any statement about making source code for the described methodology available, nor does it provide any links to a code repository. |
| Open Datasets | No | This paper focuses on theoretical research regarding constraint networks and does not involve the use of datasets for training or empirical evaluation. Therefore, there is no mention of publicly available datasets. |
| Dataset Splits | No | This paper is theoretical and does not conduct empirical experiments with data. Therefore, it does not describe dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper that focuses on mathematical properties and complexity. It does not describe any computational experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is purely theoretical and does not describe any software implementation or dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and focuses on proofs and analysis of constraint networks. It does not include any experimental setup details, hyperparameters, or training configurations. |