New Length Dependent Algorithm for Maximum Satisfiability Problem
Authors: Vasily Alferov, Ivan Bliznets3634-3641
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the computational complexity of the MAXIMUM SATISFIABILITY problem in terms of the length L of a given formula. We present an algorithm with running time O(1.0927L), hence, improving the previously known best upper bound O(1.1058L)...Our algorithms follow standard branch-and-bound technique enhanced with measure-and-conquer approach. As other algorithms with such technique our algorithms consist of reduction and branching rules. |
| Researcher Affiliation | Collaboration | Vasily Alferov,3 Ivan Bliznets 1 2 1 HSE University 2 St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences 3 Jet Brains Research vasily.v.alferov@gmail.com, iabliznets@gmail.com |
| Pseudocode | Yes | R-Rule 1. Let x be a variable such that both literals x and x are contained in the same clause x x C. Then we can remove this clause, i.e. ((x x C) F , k) (F , k 1). (And other similar R-Rules and B-Rules throughout the paper presenting structured steps for the algorithm) |
| Open Source Code | No | The paper does not contain any statement or link providing concrete access to the source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper on algorithmic complexity and does not use or refer to any datasets. |
| Dataset Splits | No | This is a theoretical paper on algorithmic complexity and does not involve dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe any experimental setup details such as hyperparameters or training configurations. |