Ranking Sets of Objects: The Complexity of Avoiding Impossibility Results
Authors: Jan Maly
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we determine the computational complexity of recognizing such families. We show that it is Πp 2-complete to decide for a given family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for all linear orders on the objects if the lifted order needs to be total. Furthermore, we show that the problem remains co NP-complete if the lifted order can be incomplete. Additionally, we show that the complexity of these problems can increase exponentially if the family of sets is not given explicitly but via a succinct domain restriction. Finally, we show that it is NP-complete to decide for a family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for at least one linear order on the objects. |
| Researcher Affiliation | Academia | Jan Maly EMAIL Institute for Logic and Computation, TU Wien, Vienna, Austria |
| Pseudocode | No | The paper primarily focuses on theoretical proofs, theorems, and complexity analysis of logical problems. It describes reductions and constructions in a mathematical prose format rather than providing structured pseudocode or algorithm blocks. For example, in Section 3.1, it states, "We will produce an instance (X, X) of Strong DIS-LO-Orderability" and "We construct the order on X in several steps," detailing the process in text rather than in a formal algorithm block. |
| Open Source Code | No | The paper is theoretical and focuses on computational complexity results and mathematical proofs. It does not describe any software implementation or empirical experiments, therefore, it does not provide access to source code for any methodology presented. |
| Open Datasets | No | The paper is theoretical and deals with abstract "families of sets" as mathematical constructs for complexity analysis and proofs (e.g., "whether a family of sets is strongly orderable"). It does not conduct empirical studies that would involve real-world or simulated datasets. Therefore, there are no mentions of publicly available datasets, links, DOIs, or citations to specific data repositories. |
| Dataset Splits | No | The paper is purely theoretical, focusing on computational complexity and impossibility results for ranking sets of objects. It does not involve empirical experiments using datasets, and therefore, the concept of training, test, or validation splits for data is not applicable or mentioned. |
| Hardware Specification | No | The paper is theoretical, centered on computational complexity and mathematical proofs. It does not describe any experimental setup or empirical evaluation that would require specific hardware. Therefore, no hardware specifications (like CPU, GPU, or memory details) are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity proofs and reductions. It does not describe any experimental implementation or empirical evaluation that would require specific software dependencies with version numbers. While it mentions "Sat-solving methods" in relation to prior work, this is not a dependency for the authors' own presented research. |
| Experiment Setup | No | The paper is entirely theoretical, presenting computational complexity results and mathematical proofs. It does not involve any empirical experiments, model training, or system-level testing. Consequently, there are no details provided regarding experimental setup, hyperparameters, or training configurations. |