Bounded queries in recursion theory

zbMath0936.03038MaRDI QIDQ1806349

William I. Gasarch, Georgia A. Martin

Publication date: 2 November 1999

Published in: Progress in Computer Science and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

computational complexityhierarchiesrelative computabilityoraclequerysubjectivereducibilitiessupportiveterseverbose

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Related Items

The complexity of finding SUBSEQ\((A)\), Learning and classifying, Some connections between bounded query classes and non-uniform complexity., Weak cardinality theorems, The communication complexity of enumeration, elimination, and selection, The complexity of ODD_n^A, Choosing, agreeing, and eliminating in communication complexity, On the query complexity of finding a local maximum point.