The Opacity of Backbones
Authors: Lane Hemaspaandra, David Narvez
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper studies the nontransparency of backbones. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values, a S, of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone S is intractable. Further, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency. We will provide proofs in Section 3. |
| Researcher Affiliation | Academia | Lane A. Hemaspaandra Department of Computer Science University of Rochester Rochester, NY 14627, USA David E. Narv aez College of Computing and Information Sciences Rochester Institute of Technology Rochester, NY 14623, USA |
| Pseudocode | No | The paper describes theoretical constructions, such as the Galil-Cook function and its properties, but it does not present any structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | we have made available a detailed construction we have built that accomplishes this, in the full technical report version of this paper, which is available online as Hemaspaandra and Narv aez, 2016; the construction involves exploiting encoding headroom that one can in some sense piggyback on top of an arbitrary implementation of the Cook-Karp-Levin Reduction. |
| Open Datasets | No | The paper is theoretical and focuses on proofs regarding boolean formulas and complexity classes. It does not conduct empirical experiments using datasets for training, validation, or testing. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any experimental setup or the specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementations or specific software dependencies with version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details, hyperparameters, or system-level training settings. |