On adaptive versus nonadaptive bounded query machines

DOI10.1016/0304-3975(91)90171-WMaRDI QIDQ808242zbMATH OpenOpenAlexFDO

Authors Ker-I Ko

Publication date 1991

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

Full work available at URL https://doi.org/10.1016/0304-3975(91)90171-w

zbMATH Keywords

adaptive computationbounded query machinesnonadaptive computation

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On monotonous oracle machines
• On bounded query machines
• Bounded Query Classes
• Nondeterministic bounded query reducibilities
• Some connections between bounded query classes and non-uniform complexity.

Cites work

• A comparison of polynomial time reducibilities
• Bounded queries to SAT and the Boolean hierarchy
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• scientific article; zbMATH DE number 4075037 (Why is no real title available?)
• On Sets Truth-Table Reducible to Sparse Sets
• Terse, superterse, and verbose sets
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

Cited in

(4)

• On bounded query machines
• Nondeterministic bounded query reducibilities
• In Memoriam: Ker-I Ko (1950–2018)
• On monotonous oracle machines

This page was built for publication: On adaptive versus nonadaptive bounded query machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808242)