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.











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)