Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega.
George BarmpaliasNan FangAndrew Lewis-PyePublished in: J. Comput. Syst. Sci. (2016)
Keyphrases
- worst case
- asymptotically optimal
- upper bound
- asymptotic optimality
- lower bound
- tight bounds
- error bounds
- closed form expressions
- rates of convergence
- optimal design
- optimal solution
- np hard
- average case
- large deviations
- minimum cost
- worst case bounds
- upper and lower bounds
- database
- oracle database
- closed form
- databases