The Density of Weakly Complete Problems under Adaptive Reductions
Copyright policy )The Density of Weakly Complete Problems under Adaptive Reductions
Summary: Given a real number \(\alpha < 1\), every language that is weakly \(\leq_{n^{\alpha/2}}\)-\(T^{P}\)-hard for \(E\) or weakly \(\leq_{n^{\alpha}}\)-\(T^{P}\)-hard for \(E_{2}\) is shown to be exponentially dense. This simultaneously strengthens the results of \textit{J. H. Lutz} and \textit{E. Mayordomo} [ibid. 23, No. 4, 762-779 (1994; Zbl 0809.68069)] and \textit{B. Fu} [ibid. 24, No. 5, 1082-1090 (1995; Zbl 0845.68046)].
- Iowa State University United States
weakly complete problems, resource-bounded measure, computational complexity, polynomial reductions, Complexity classes (hierarchies, relations among complexity classes, etc.), complexity classes
weakly complete problems, resource-bounded measure, computational complexity, polynomial reductions, Complexity classes (hierarchies, relations among complexity classes, etc.), complexity classes
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!