On sets polynomially enumerable by iteration

DOI10.1016/0304-3975(91)90388-IMaRDI QIDQ1176233zbMATH OpenOpenAlexFDO

Authors S. Singh, Lane A. Hemaspaandra, Albrecht Hoene, Dirk Siefkes, P. R. Young

Publication date 25 June 1992

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90388-i

zbMATH Keywords

invertibly \(i\)-enumerable setsiteratively enumerable setsmonotonicity of enumeration functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• scientific article; zbMATH DE number 4106271
• Logical Approaches to Computational Barriers
• Toward a Theory of Enumerations
• Enumerative counting is hard

Cites work

• A Theorem on Recursively Enumerable Classes and Splinters
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Characterizing the orders changed by program translators
• Complete Problems and Strong Polynomial Reducibilities
• Complete sets and the polynomial-time hierarchy
• Complexity classes without machines: on complete languages for UP
• Complexity Measures for Public-Key Cryptosystems
• Computation times of NP sets of different densities
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 4155842 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 15884 (Why is no real title available?)
• scientific article; zbMATH DE number 17806 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 403952 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Near-Testable Sets
• On Isomorphisms and Density of NP and Other Complete Sets
• On one-one polynomial time equivalence relations
• On Pseudo‐Creative Sets, Splinters, and Bounded‐Truth‐Table Reducibility
• On Semi-Cylinders, Splinters, and Bounded-Truth-Table Reducibility
• On Sets with Efficient Implicit Membership Tests
• On sparse oracles separating feasible complexity classes
• On the complexity of ranking
• On the construction of parallel computers from various basis of Boolean functions
• On the power of parity polynomial time
• On the structure and complexity of infinite sets with minimal perfect hash functions
• One-way functions and the nonisomorphism of NP-complete sets
• Optimal Approximations and Polynomially Levelable Sets
• P-Printable Sets
• Polynomial Time Enumeration Reducibility
• Random generation of combinatorial structures from a uniform distribution
• Recursive digraphs, splinters and cylinders
• Reductions among polynomial isomorphism types
• Relative complexity of checking and evaluating
• Relativized Questions Involving Probabilistic Algorithms
• Sets with small generalized Kolmogorov complexity
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Splinters of recursive functions
• The complexity of ranking simple languages
• The polynomial-time hierarchy
• Toward a Theory of Enumerations
• Zum Begriff der Axiomatisierbarkeit. Herrn Professor Dr. Erhard Schmidt zum 75. Geburtstage als ein Symbol der Verehrung und Dankbarkeit der Sechule von Münster

Cited in

(6)

• Polynomial-time compression
• Listing graphs that satisfy first-order sentences
• Scalability and the isomorphism problem
• Nil Bohr₀-sets and polynomial recurrence
• ON THE SIZE OF SETS IN A POLYNOMIAL VARIANT OF A PROBLEM OF DIOPHANTUS
• Polynomial-time axioms of choice and polynomial-time cardinality

This page was built for publication: On sets polynomially enumerable by iteration

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