A note on the best-case complexity (Q1120281)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the best-case complexity |
scientific article |
Statements
A note on the best-case complexity (English)
0 references
1989
0 references
Four aspects of complexity are discussed: almost everywhere vs. infinitely often and best-case vs. worst-case. Three main results are proved. First, the most of the basic propositions of almost everywhere worst case complexity can be extended to the other cases: almost everywhere best- case, infinitely often best-case and infinitely often worst-case. Second, there exist languages recognized almost everywhere in worst time bound \(g(n)\) that cannot be recognized in almost everywhere best-case time complexity \(f(n)\), where \(g(n)\) and \(f(n)\) are slightly separated. Third, there exist languages not even computable infinitely often in best-case space \(f(n)\) that are easy to compute almost everywhere in worst- case space \(g(n)\), with \(f\) and \(g\) very close. The last section includes some open questions and discusses the issue of nondeterminism.
0 references
complexity theory
0 references
almost everywhere
0 references
infinitely often
0 references
best-case
0 references
worst- case
0 references