Self-reducibility

DOI10.1016/0022-0000(90)90025-GzbMath0718.68037OpenAlexW70814323MaRDI QIDQ2639637

José L. Balcázar

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90025-g

zbMATH Keywords

NP-completeoracle Turing machineself-reducibilitydeterministic time classesnondeterministic space classesreducibility to context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, Revisiting a result of Ko, Space-efficient recognition of sparse self-reducible languages, Geometric sets of low information content, Quasi-linear truth-table reductions to \(p\)-selective sets, Symbolic techniques in satisfiability solving, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, P-immune sets with holes lack self-reducibility properties., A note on the self-witnessing property of computational problems, Upper bounds for the complexity of sparse and tally descriptions, Helping by unambiguous computation and probabilistic computation, New collapse consequences of NP having small circuits, On the autoreducibility of functions, Competing provers yield improved Karp-Lipton collapse results, Monotonous and randomized reductions to sparse sets

Cites Work

• Turing machines that take advice
• On self-reducibility and weak P-selectivity
• Space-bounded hierarchies and probabilistic computations
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy and sparse oracles
• A Note on Sparse Complete Sets
• Nondeterministic Space is Closed under Complementation
• Alternation
• On the Tape Complexity of Deterministic Context-Free Languages
• The Hardest Context-Free Language
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Time and tape complexity of pushdown automaton languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item