Terse, superterse, and verbose sets

DOI10.1006/INCO.1993.1014MaRDI QIDQ1803657zbMATH OpenOpenAlexFDO

Authors Richard Beigel, William Gasarch, John Gill, James C. jun. Owings

Publication date 29 June 1993

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1993.1014

zbMATH Keywords

decidabilityqueries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 517081
• scientific article; zbMATH DE number 512828
• scientific article; zbMATH DE number 1678392
• The complexity of ODD_n^A
• scientific article; zbMATH DE number 1114037

Cited in

(30)

• Polynomial terse sets
• Bounded query classes and the difference hierarchy
• A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
• The complexity of finding SUBSEQ(A)
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Enumerative counting is hard
• The power of frequency computation
• Binary search and recursive graph problems
• On the structures inside truth-table degrees
• Nondeterministic bounded query reducibilities
• Some connections between bounded query classes and non-uniform complexity.
• The complexity of ODD_n^A
• Choosing, agreeing, and eliminating in communication complexity
• scientific article; zbMATH DE number 1678392 (Why is no real title available?)
• The communication complexity of enumeration, elimination, and selection
• Frequency computation and bounded queries
• Bounded queries to SAT and the Boolean hierarchy
• A proof of Beigel's cardinality conjecture
• Learning recursive functions from approximations
• Enumerations of the Kolmogorov function
• Learning via queries and oracles
• Bi-immunity results for cheatable sets
• On quasilinear-time complexity theory
• Quantifying the amount of verboseness
• Unbounded search and recursive graph problems
• Weakly semirecursive sets and r.e. orderings
• Extremes in the degrees of inferability
• On adaptive versus nonadaptive bounded query machines
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• scientific article; zbMATH DE number 517081 (Why is no real title available?)

This page was built for publication: Terse, superterse, and verbose sets

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