On sets polynomially enumerable by iteration
From MaRDI portal
Publication:1176233
DOI10.1016/0304-3975(91)90388-IzbMath0745.68047MaRDI QIDQ1176233
Publication date: 25 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
invertibly \(i\)-enumerable sets; iteratively enumerable sets; monotonicity of enumeration functions
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive digraphs, splinters and cylinders
- On the complexity of ranking
- On one-one polynomial time equivalence relations
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Random generation of combinatorial structures from a uniform distribution
- On the construction of parallel computers from various basis of Boolean functions
- Complexity classes without machines: on complete languages for UP
- On sparse oracles separating feasible complexity classes
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Characterizing the orders changed by program translators
- Computation times of NP sets of different densities
- Sets with small generalized Kolmogorov complexity
- One-way functions and the nonisomorphism of NP-complete sets
- The complexity of ranking simple languages
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Optimal Approximations and Polynomially Levelable Sets
- Complexity Measures for Public-Key Cryptosystems
- Splinters of recursive functions
- Relativized Questions Involving Probabilistic Algorithms
- Near-Testable Sets
- On Sets with Efficient Implicit Membership Tests
- Complete Problems and Strong Polynomial Reducibilities
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Polynomial Time Enumeration Reducibility
- P-Printable Sets
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- On Semi-Cylinders, Splinters, and Bounded-Truth-Table Reducibility
- Toward a Theory of Enumerations
- A Theorem on Recursively Enumerable Classes and Splinters
- On Pseudo‐Creative Sets, Splinters, and Bounded‐Truth‐Table Reducibility
- On the power of parity polynomial time
- Zum Begriff der Axiomatisierbarkeit. Herrn Professor Dr. Erhard Schmidt zum 75. Geburtstage als ein Symbol der Verehrung und Dankbarkeit der Sechule von Münster
