Does Increased Regularity Lower Complexity?
From MaRDI portal
\textit{J. F. Traub} and \textit{H. Woźniakowski} [A general theory of optimal algorithms (1980; Zbl 0441.68046)] conjectured that if the regularity of a class of problems increases, then the complexity decreases. In the present paper, the author investigates linear problems. Measuring the regularity by a Sobolev norm, or seminorm, the author proves a weak form of the Traub and Wozniakowski conjecture and shows that no stronger statement is possible.
Recommendations
- Uniform weak tractability of multivariate problems with increasing smoothness
- Computational complexity in worst, stochastic and average case setting on functional approximation problem of multivariate
- Tractability through increasing smoothness
- Average case complexity of linear multivariate problems. I: Theory
- Tractability of multivariate approximation in Korobov spaces with increasing smoothness in the worst case setting
Cited in
(2)
This page was built for publication: Does Increased Regularity Lower Complexity?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3219026)