Functions computable with limited access to NP

DOI10.1016/0020-0190(96)00030-0MaRDI QIDQ1351162zbMATH OpenOpenAlexFDO

Authors Ogihara, Mitsunori

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(96)00030-0

zbMATH Keywords

Computational complexityPolynomial hierarchyReducibilityNondeterministic functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Functions computable with nonadaptive queries to NP
• Computational complexity of functions
• On classes of computable functions
• scientific article; zbMATH DE number 4115977
• A new characterization of computable functions
• Computability and the Implicit Function Theorem
• scientific article; zbMATH DE number 65741
• Publication:4207514
• scientific article; zbMATH DE number 2109861
• scientific article; zbMATH DE number 4134023

Cites work

• scientific article; zbMATH DE number 512846 (Why is no real title available?)
• scientific article; zbMATH DE number 1555921 (Why is no real title available?)
• A taxonomy of complexity classes of functions
• Functions computable with nonadaptive queries to NP
• Quantitative Relativizations of Complexity Classes

Cited in

(10)

• Inverting Onto Functions and Polynomial Hierarchy
• A taxonomy of complexity classes of functions
• Does the polynomial hierarchy collapse if onto functions are invertible?
• The consequences of eliminating NP solutions
• Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)
• scientific article; zbMATH DE number 4049046 (Why is no real title available?)
• A hierarchy based on output multiplicity
• Resource-bounded Kolmogorov complexity revisited
• Reducing the number of solutions of NP functions
• Oracles That Compute Values

This page was built for publication: Functions computable with limited access to NP

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