Terse, superterse, and verbose sets
From MaRDI portal
Publication:1803657
DOI10.1006/inco.1993.1014zbMath0781.68057OpenAlexW1995304514MaRDI QIDQ1803657
William I. Gasarch, Richard Beigel, 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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ The power of frequency computation ⋮ Polynomial terse sets ⋮ Bounded query classes and the difference hierarchy ⋮ Learning recursive functions from approximations ⋮ Nondeterministic bounded query reducibilities ⋮ Unbounded search and recursive graph problems ⋮ Binary search and recursive graph problems ⋮ Bi-immunity results for cheatable sets ⋮ On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Bounded queries to SAT and the Boolean hierarchy ⋮ Frequency computation and bounded queries ⋮ On quasilinear-time complexity theory ⋮ On the structures inside truth-table degrees ⋮ Weakly semirecursive sets and r.e. orderings ⋮ The communication complexity of enumeration, elimination, and selection ⋮ The complexity of ODDnA ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Enumerations of the Kolmogorov function ⋮ Enumerative counting is hard ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Learning via queries and oracles ⋮ On adaptive versus nonadaptive bounded query machines ⋮ Extremes in the degrees of inferability
This page was built for publication: Terse, superterse, and verbose sets
