Investigations Concerning the Structure of Complete Sets
From MaRDI portal
Publication:2821693
DOI10.1007/978-3-319-05446-9_2zbMath1345.68142OpenAlexW91166391MaRDI QIDQ2821693
Publication date: 22 September 2016
Published in: Perspectives in Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-05446-9_2
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The isomorphism conjecture for constant depth reductions
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Isomorphisms and 1-L reductions
- Rudimentary reductions revisited
- On p-creative sets and p-completely creative sets
- Space-bounded reducibility among combinatorial problems
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Polynomial-time isomorphism of 1-L-complete sets
- On the isomorphism conjecture for weak reducibilities
- Collapsing degrees via strong computation
- Circuit minimization problem
- Parity, circuits, and the polynomial-time hierarchy
- Problems complete for deterministic logarithmic space
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- A First-Order Isomorphism Theorem
- NP-Creative sets: A new class of creative sets in NP
- The degree structure of 1-L reductions
- Strong Reductions and Isomorphism of Complete Sets
- Recursively enumerable sets of positive integers and their decision problems
- Reducing the complexity of reductions
This page was built for publication: Investigations Concerning the Structure of Complete Sets
