Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
On Minimum Representations of Matched Formulas
Authors: O. Cepek, S. Gursky, P. Kucera
JAIR 2014 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The main result of this paper deals with the structure of clause minimum CNFs. We prove here that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched. The paper is structured as follows. We start by introducing the necessary notation, definitions and basic results in Section 2. In Section 3 we prove that testing logical equivalence for matched CNFs is co-NP-complete and further use the idea from this proof to show that BM for matched formulas is Σp 2-complete. This is a known fact, but the current proof is much shorter and simpler. Section 4 studies prime representations of functions defined by matched CNFs (possibly nonprime). We prove that every such function has at least one prime representation which is matched. Finally, in Section 5 we study the structure of clause minimum representations of functions defined by matched CNFs. Using the result from Section 4 we prove that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched. |
| Researcher Affiliation | Academia | Ondřej Čepek EMAIL Štefan Gurský EMAIL Petr Kučera EMAIL Charles University in Prague Faculty of Mathematics and Physics Department of Theoretical Computer Science Malostranské nám. 25, 118 00 Praha 1, Czech Republic |
| Pseudocode | No | The paper focuses on theoretical proofs, definitions, lemmas, and theorems related to Boolean formulas and their representations. It does not include any sections labeled 'Pseudocode' or 'Algorithm', nor does it present structured, code-like procedures. |
| Open Source Code | No | The paper does not contain any statements about releasing code, links to repositories, or mentions of code in supplementary materials. |
| Open Datasets | No | This paper is theoretical and focuses on mathematical proofs and complexity results for Boolean formulas; therefore, it does not use or reference any datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve experiments with datasets, so there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions for experimental reproduction. |
| Experiment Setup | No | This paper is purely theoretical, presenting mathematical proofs and complexity analysis. It does not describe any experimental setups, hyperparameters, or training configurations. |