On the Structure of Bounded Queries to Arbitrary NP Sets

DOI10.1137/0221045zbMath0749.68034OpenAlexW2167277189MaRDI QIDQ4016404

Richard Chang

Publication date: 14 December 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6784

zbMATH Keywords

sparse setsBoolean hierarchypolynomial-time hierarchybounded queriesnonuniform computation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (3)

Some connections between bounded query classes and non-uniform complexity. ⋮ On the asymmetric complexity of the group-intersection problem ⋮ Bounded queries to arbitrary sets

This page was built for publication: On the Structure of Bounded Queries to Arbitrary NP Sets