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

1-tt-reductionsalmost completenesslength-increasing one-one reductionsmany-one reductionsresource-bounded measureresource-bounded reducibilitiesweak completeness

Mathematics Subject Classification ID

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

Review text

The authors consider the class \({\mathbf E}\) of sets being computable in (linear) exponential time. They define the concept of almost completeness for the class \({\mathbf E}\) under some given reducibility if the class of languages in \({\mathbf E}\) that do not reduce to this set has measure 0 in \({\mathbf E}\), in the sense of Lutz's resource-bounded measure theory, based on polynomial-time computable martingales. The main result states that there are sets in \({\mathbf E}\) being almost complete but not complete under polynomial-time many-one reductions.

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

• A comparison of polynomial time completeness notions
• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• Genericity and measure for exponential time
• 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?)
• 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 complete problems are not rare
• Weakly Hard Problems

Cited in

(8)

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

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)