On the Subexponential-Time Complexity of CSP
Authors: Ronald de Haan, Iyad Kanj, Stefan Szeider
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our lower bounds are subject to the Exponential Time Hypothesis (ETH), even though some of our results are derived under weaker complexity-theoretic hypotheses (Proposition 2, Proposition 3, and Proposition 10). The structural parameters in a CSP instance that we focus on (when relevant) are: the (instance) size, the domain size, the number of constraints, the arity (i.e., maximum size of a constraint scope), the maximum degree (i.e., the maximum number of occurrences of a variable), and the treewidth of the primal or incidence graph. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem. |
| Researcher Affiliation | Academia | Ronald de Haan EMAIL Vienna University of Technology Vienna, Austria; Iyad Kanj EMAIL School of Computing, De Paul University Chicago, USA; Stefan Szeider EMAIL Vienna University of Technology Vienna, Austria. |
| Pseudocode | No | The paper describes algorithmic approaches and theoretical reductions in natural language within the main text (e.g., in the proof of Theorem 1 and Theorem 6), but it does not present any formal pseudocode blocks, algorithm figures, or code-like structured steps explicitly labeled as 'Pseudocode' or 'Algorithm'. |
| Open Source Code | No | The paper makes no mention of releasing any source code, providing links to code repositories, or including code in supplementary materials for the methodology described. It is a theoretical paper focusing on complexity analysis. |
| Open Datasets | No | The paper is theoretical and focuses on the subexponential-time complexity of Constraint Satisfaction Problems (CSP) and related variants. It analyzes algorithms and complexity classes but does not utilize or refer to any specific datasets for empirical evaluation, nor does it provide concrete access information for any open datasets. |
| Dataset Splits | No | As the paper is theoretical and does not involve empirical experiments with specific datasets, there is no mention or description of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity analysis and algorithm design. It does not describe any experimental setup or specify hardware (like GPU/CPU models, processors, or memory) used for running experiments. |
| Software Dependencies | No | The paper is a theoretical work on computational complexity and does not describe any empirical experiments. Therefore, it does not mention specific software dependencies or their version numbers (e.g., Python, PyTorch, CPLEX) that would be required for replication. |
| Experiment Setup | No | This is a theoretical paper presenting complexity analysis and algorithmic bounds. It does not include any experimental setup details, hyperparameter values, training configurations, or other specific system-level settings relevant to empirical experiments. |