On monotonous oracle machines

DOI10.1007/3-540-59175-3_108zbMath1495.68057OpenAlexW1572403331MaRDI QIDQ5096350

Martin Mundhenk

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_108

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• More complicated questions about maxima and minima, and some closures of NP
• Reductions on NP and p-selective sets
• A comparison of polynomial time reducibilities
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• Bounded Query Classes
• Relating Equivalence and Reducibility to Sparse Sets
• On the Computational Complexity of Small Descriptions
• SPARSE Reduces Conjunctively to TALLY
• Upper bounds for the complexity of sparse and tally descriptions
• Reducibility among Combinatorial Problems
• The complexity of theorem-proving procedures

This page was built for publication: On monotonous oracle machines