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
