Constraint Optimization over Semirings
Authors: A. Pavan, Kuldeep S. Meel, N. V. Vinodchandran, Arnab Bhattacharyya
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The present work investigates the complexity of constraint optimization problems over semirings. The generic optimization problem we study is the following: Given a propositional formula ϕ over n variable and a semiring (K, +, , 0, 1), find the maximum value over all possible interpretations of ϕ over K. ... We first show that for general propositional formulas in negation normal form, opt Conf Val and opt Conf are in FPNP. We then investigate opt Conf when the input formula ϕ is represented in the conjunctive normal form. For CNF formulae, we first derive an upper bound on the value of opt Conf as a function of the number of maximum satisfiable clauses. ... Building on this we establish that opt Conf for CNF formulae is hard for the complexity class FPNP[log]. We also design polynomial-time approximation algorithms and establish an inapproximability for opt Conf Val. We establish similar complexity results for these optimization problems over other semirings including tropical, fuzzy, and access control semirings. |
| Researcher Affiliation | Academia | 1 Iowa State University 2 National University of Singapore 3 University of Nebraska-Lincoln |
| Pseudocode | No | The paper describes algorithms and theoretical results, but it does not include any explicitly labeled 'Pseudocode' or 'Algorithm' blocks, nor does it present structured steps formatted like code. |
| Open Source Code | No | The paper does not contain any statement about releasing source code for the described methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is a theoretical work focusing on computational complexity and algorithms. It does not describe experiments involving datasets for training, validation, or testing, nor does it mention specific dataset availability. |
| Dataset Splits | No | The paper is a theoretical work focusing on computational complexity and algorithms. It does not describe experiments involving datasets for training, validation, or testing, nor does it mention specific dataset availability. |
| Hardware Specification | No | The paper is theoretical and does not describe computational experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper focuses on theoretical computer science, including computational complexity and algorithm design. It does not mention any specific software dependencies or versions required for implementation or replication. |
| Experiment Setup | No | The paper is theoretical and does not detail any empirical experimental setups, hyperparameters, or system-level training settings. |