Terse, superterse, and verbose sets

DOI10.1006/INCO.1993.1014zbMATH Open0781.68057OpenAlexW1995304514MaRDI QIDQ1803657FDOQ1803657

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

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

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)

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
• The communication complexity of enumeration, elimination, and selection
• Title not available (Why is that?)
• Frequency computation and bounded queries
• Enumerations of the Kolmogorov function
• A proof of Beigel's cardinality conjecture
• Bounded queries to SAT and the Boolean hierarchy
• Learning recursive functions from approximations
• 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
• Title not available (Why is that?)

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)