کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4606914 1631410 2015 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Notes on (s,t)(s,t)-weak tractability: A refined classification of problems with (sub)exponential information complexity
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
پیش نمایش صفحه اول مقاله
Notes on (s,t)(s,t)-weak tractability: A refined classification of problems with (sub)exponential information complexity
چکیده انگلیسی

In the last 20 years a whole hierarchy of notions of tractability was proposed and analyzed by several authors. These notions are used to classify the computational hardness of continuous numerical problems S=(Sd)d∈NS=(Sd)d∈N in terms of the behavior of their information complexity n(ε,Sd)n(ε,Sd) as a function of the accuracy εε and the dimension dd. By now a lot of effort was spent on either proving quantitative positive results (such as, e.g., the concrete dependence on εε and dd within the well-established framework of polynomial tractability), or on qualitative negative results (which, e.g., state that a given problem suffers from the so-called curse of dimensionality). Although several weaker types of tractability were introduced recently, the theory of information-based complexity still lacks a notion which allows to quantify the exact (sub-/super-) exponential dependence of n(ε,Sd)n(ε,Sd) on both parameters εε and dd. In this paper we present the notion of (s,t)(s,t)-weak tractability which attempts to fill this gap. Within this new framework the parameters ss and tt are used to quantitatively refine the huge class of polynomially intractable problems. For linear, compact operators between Hilbert spaces we provide characterizations of (s,t)(s,t)-weak tractability w.r.t. the worst case setting in terms of singular values. In addition, our new notion is illustrated by classical examples which recently attracted some attention. In detail, we study approximation problems between periodic Sobolev spaces and integration problems for classes of smooth functions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Approximation Theory - Volume 200, December 2015, Pages 227–258
نویسندگان
, ,