Investigations concerning the structure of complete sets

DOI10.1007/978-3-319-05446-9_2MaRDI QIDQ2821693zbMATH OpenOpenAlexFDO

Authors Eric Allender

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

zbMATH Keywords

Berman-Hartmanis conjecturecreativityisomorphismNP-completenessuniversality

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On correlations between complete sets
• On existence of complete sets for bounded reducibilities
• On p-creative sets and p-completely creative sets
• scientific article; zbMATH DE number 88948
• Productive functions and isomorphisms

Cites work

• A First-Order Isomorphism Theorem
• Circuit minimization problem
• Collapsing degrees via strong computation
• scientific article; zbMATH DE number 5604770 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 1860651 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Isomorphisms and 1-L reductions
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• NP-Creative sets: A new class of creative sets in NP
• On Isomorphisms and Density of NP and Other Complete Sets
• On p-creative sets and p-completely creative sets
• On the isomorphism conjecture for weak reducibilities
• Parity, circuits, and the polynomial-time hierarchy
• Polynomial-time isomorphism of 1-L-complete sets
• Problems complete for deterministic logarithmic space
• Recursively enumerable sets of positive integers and their decision problems
• Reducing the complexity of reductions
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Rudimentary reductions revisited
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Space-bounded reducibility among combinatorial problems
• Strong Reductions and Isomorphism of Complete Sets
• The degree structure of 1-L reductions
• The isomorphism conjecture for constant depth reductions

Cited in

(3)

• Study of the bounds on the number of basic sets in a test.
• The Complexity of Complexity
• Constructions of complete sets

This page was built for publication: Investigations concerning the structure of complete sets

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