On helping by robust oracle machines

DOI10.1016/0304-3975(87)90078-8zbMath0635.68039OpenAlexW1982143949MaRDI QIDQ1097695

Ker-I. Ko

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90078-8

zbMATH Keywords

complexity theorysparsenessNPself-reducibilityhelpingrobust oracle Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, Revisiting a result of Ko, On helping by parity-like languages, Query-monotonic Turing reductions, Polynomial time quantum computation with advice, Promise problems and access to unambiguous computation, Degrees and reducibilities of easy tally sets, The Helping Hierarchy, A result relating disjunctive self-reducibility to P-immunity, Bi-immunity results for cheatable sets, Fault-tolerance and complexity (Extended abstract), In Memoriam: Ker-I Ko (1950–2018), The Power of Self-Reducibility: Selectivity, Information, and Approximation, On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets, Constructive complexity, On quasilinear-time complexity theory, Helping by unambiguous computation and probabilistic computation, Logarithmic advice classes, On being incoherent without being very hard, Classes of bounded nondeterminism, Probabilistic complexity classes and lowness, The structure of logarithmic advice complexity classes, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, Padding, commitment and self-reducibility, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

Cites Work

• Unnamed Item
• A low and a high hierarchy within NP
• On self-reducibility and weak P-selectivity
• Robust algorithms: a different approach to oracles
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Relative complexity of checking and evaluating
• Complete sets and the polynomial-time hierarchy
• Complexity of Presburger arithmetic with fixed quantifier dimension
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• The complexity of theorem-proving procedures