A Multivariate Complexity Analysis of Qualitative Reasoning Problems
Authors: Leif Eriksson, Victor Lagerkvist
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter n (e.g., the number of variables) and a coarse-grained parameter k expected to be relatively small. We introduce the classes FPE and XE of problems solvable in f(k) 2O(n), respectively f(k)n, time, and prove several fundamental properties of these classes. We proceed by studying temporal reasoning problems and (1) show that the PARTIALLY ORDERED TIME problem of effective width k is solvable in 16kn time and is thus included in XE, and (2) that the network consistency problem for ALLEN S INTERVAL ALGEBRA with no interval overlapping with more than k others is solvable in (2nk)2k 2n time and is included in FPE. |
| Researcher Affiliation | Academia | Leif Eriksson and Victor Lagerkvist Department of Computer and Information Science, Link oping University, Link oping, Sweden {leif.eriksson, victor.lagerkvist}@liu.se |
| Pseudocode | No | The paper describes the principles and recursive functions of its algorithms (e.g., "we define a recursive function X", "define a recurrence relation R"), but it does not present them in a structured pseudocode block or a clearly labeled algorithm section. |
| Open Source Code | No | The paper does not contain any statements about releasing source code for the described methodology or provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis and algorithm design; it does not describe using or accessing any specific dataset for training. |
| Dataset Splits | No | The paper is theoretical and focuses on complexity analysis; it does not describe any dataset splits for validation or other empirical evaluation. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity analysis; it does not describe any hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on complexity analysis; it does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis; it does not describe any experimental setup details, hyperparameters, or training configurations. |