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