Functions computable with limited access to NP

DOI10.1016/0020-0190(96)00030-0zbMath0875.68427OpenAlexW2000107242MaRDI QIDQ1351162

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)

Related Items (4)

Resource-bounded kolmogorov complexity revisited ⋮ The consequences of eliminating NP solutions ⋮ A hierarchy based on output multiplicity ⋮ Reducing the number of solutions of NP functions

Cites Work

• A taxonomy of complexity classes of functions
• Functions computable with nonadaptive queries to NP
• Quantitative Relativizations of Complexity Classes
• Unnamed Item
• Unnamed Item

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