Almost complete sets.
type: Item
instance of: scholarly article
title: Almost complete sets.
zbMATH Open document ID: 1048.03032
DOI: 10.1016/S0304-3975(03)00262-7
author: Wolfgang Merkle
author: Jan Reimann
author: Sebastiaan A. Terwijn
author: Klaus Ambos-Spies
published in: Theoretical Computer Science
publication date: 2004-03-14T00:00:00Z
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.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2056796
zbMATH Keywords: resource-bounded measure
zbMATH Keywords: weak completeness
zbMATH Keywords: almost completeness
zbMATH Keywords: resource-bounded reducibilities
zbMATH Keywords: many-one reductions
zbMATH Keywords: length-increasing one-one reductions
zbMATH Keywords: 1-tt-reductions
MaRDI profile type: Publication
cites work: Q4536350
cites work: Q4218120
cites work: Q4348122
cites work: Genericity and measure for exponential time
cites work: Resource bounded randomness and weakly complete problems
cites work: Q4321931
cites work: A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
cites work: On 1-truth-table-hard languages
cites work: Weakly complete problems are not rare
cites work: The Complexity and Distribution of Hard Problems
cites work: Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
cites work: Q4273947
cites work: Almost everywhere high nonuniform complexity
cites work: Weakly Hard Problems
cites work: Q4359463
cites work: Almost every set in exponential time is P-bi-immune
cites work: Q4231907
cites work: A comparison of polynomial time completeness notions
full work available at URL: s0304-3975(03)00262-7
OpenAlex ID: W2019482663
description: scientific article; zbMATH DE number 2056796