Self-reducibility
In the paper the ldq-self reducibility, wdq-self reducibility, and logspace self-reducibility are defined (ldq stands for length-decreasing queries and wdq for word-decreasing queries). The properties derived from the definitions regarding the interconnection between uniform and nonuniform complexity classes are used to prove known results and to obtain new ones regarding deterministic time classes, nondeterministic space classes and reducibility to context-free languages. From new results obtained here, we remark the following: i) Let A be a logspace self-reducible set. If A \(\in NLOG/\log\) then A \(\in NLOG;\) ii) Let M be a pushdown automaton with no \(\lambda\)-transition which accepts by empty store. There is a set A \(\in LOG(CFL)\) which is logspace self-reducible such that L(M) \(\in DLOG(A)\). Furthermore, if M is deterministic then A \(\in LOG(DCFL)\).
- A Note on Sparse Complete Sets
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- scientific article; zbMATH DE number 3917710 (Why is no real title available?)
- scientific article; zbMATH DE number 4087055 (Why is no real title available?)
- scientific article; zbMATH DE number 3594673 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- Nondeterministic Space is Closed under Complementation
- On self-reducibility and weak P-selectivity
- On the Tape Complexity of Deterministic Context-Free Languages
- Space-bounded hierarchies and probabilistic computations
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The Hardest Context-Free Language
- The polynomial-time hierarchy and sparse oracles
- Time and tape complexity of pushdown automaton languages
- Turing machines that take advice
- Space-efficient recognition of sparse self-reducible languages
- Geometric sets of low information content
- Quasi-linear truth-table reductions to \(p\)-selective sets
- P-immune sets with holes lack self-reducibility properties.
- Competing provers yield improved Karp-Lipton collapse results
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Reductivity
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- Revisiting a result of Ko
- scientific article; zbMATH DE number 4022646 (Why is no real title available?)
- scientific article; zbMATH DE number 4092778 (Why is no real title available?)
- scientific article; zbMATH DE number 4096780 (Why is no real title available?)
- Intrinsic Reducibilities
- New collapse consequences of NP having small circuits
- Monotonous and randomized reductions to sparse sets
- scientific article; zbMATH DE number 1839442 (Why is no real title available?)
- Upper bounds for the complexity of sparse and tally descriptions
- Strong self-reducibility precludes strong immunity
- Selfdecomposable fields
- scientific article; zbMATH DE number 2213919 (Why is no real title available?)
- A note on the self-witnessing property of computational problems
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Some results on selectivity and self-reducibility
- Helping by unambiguous computation and probabilistic computation
- From amortized to worst case delay in enumeration algorithms
- Symbolic techniques in satisfiability solving
- On the autoreducibility of functions
This page was built for publication: Self-reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639637)
