Almost complete sets.

DOI10.1016/S0304-3975(03)00262-7MaRDI QIDQ1426448zbMATH OpenOpenAlexFDO

Authors Wolfgang Merkle, Jan Reimann, Sebastiaan A. Terwijn, Klaus Ambos-Spies

Publication date 14 March 2004

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

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00262-7

zbMATH Keywords

resource-bounded measureweak completenessalmost completeness1-tt-reductionslength-increasing one-one reductionsmany-one reductionsresource-bounded reducibilities

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• scientific article; zbMATH DE number 1500533
• scientific article; zbMATH DE number 1759402
• Comparing Reductions to NP-Complete Sets
• Hard sets are hard to find
• scientific article; zbMATH DE number 1335891

Cites work

• scientific article; zbMATH DE number 1222581 (Why is no real title available?)
• scientific article; zbMATH DE number 1261804 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 1048036 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• scientific article; zbMATH DE number 1759402 (Why is no real title available?)
• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
• A comparison of polynomial time completeness notions
• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• Genericity and measure for exponential time
• On 1-truth-table-hard languages
• Resource bounded randomness and weakly complete problems
• The Complexity and Distribution of Hard Problems
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weakly Hard Problems
• Weakly complete problems are not rare

Cited in

(6)

• Polynomial-time reducibilities and ``almost all oracle sets
• A note on measuring in P
• scientific article; zbMATH DE number 4010508 (Why is no real title available?)
• Completeness and weak completeness under polynomial-size circuits
• Almost every set in exponential time is P-bi-immune
• Hard sets are hard to find

This page was built for publication: Almost complete sets.

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