The Power of Self-Reducibility: Selectivity, Information, and Approximation
From MaRDI portal
Publication:3297822
DOI10.1007/978-3-030-41672-0_3zbMath1440.68120arXiv1902.08299OpenAlexW3013620518MaRDI QIDQ3297822
Publication date: 20 July 2020
Published in: Complexity and Approximation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.08299
computational complexitysparse setsstructural complexityself-reducibilityenumerative countingP-selectivity
Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- A note on enumerative counting
- On self-reducibility and weak P-selectivity
- On helping by robust oracle machines
- The complexity of optimization problems
- The maximum value problem and NP real numbers
- Some observations on NP real numbers and P-selective sets
- Reductions on NP and p-selective sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Space-efficient recognition of sparse self-reducible languages
- P-immune sets with holes lack self-reducibility properties.
- Enumerative counting is hard
- Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption
- Search versus Decision for Election Manipulation Problems
- A Note on Sparse Complete Sets
- The Complexity of Enumeration and Reliability Problems
- Completeness, Approximation and Density
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Logspace Reducibility: Models and Equivalences
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Easily Checked Generalized Self-Reducibility
- Strong self-reducibility precludes strong immunity
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- The complexity theory companion
- Theory of semi-feasible algorithms
This page was built for publication: The Power of Self-Reducibility: Selectivity, Information, and Approximation
