کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4608709 | 1338374 | 2013 | 16 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Uniform weak tractability Uniform weak tractability](/preview/png/4608709.png)
We introduce a new notion of tractability which is called uniform weak tractability . A problem is uniformly weakly tractable if the information complexity n(ε,d)n(ε,d) of its dd-variate component to be solved to within εε is not exponential in any positive power of ε−1ε−1 and/or dd. This notion is stronger than weak tractability which requires that n(ε,d)n(ε,d) is not exponential only in ε−1ε−1 and dd, and weaker than quasi-polynomial tractability which requires that lnn(ε,d) is of order (1+lnε−1)(1+lnd).For the class Λall of all linear functionals, we derive necessary and sufficient conditions for a linear tensor product problem to be uniformly weakly tractable. For the class Λstd of function values, we relate the uniform weak tractability of approximation problems to already known results for weak tractability.We study uniform weak tractability in the worst case, average case and randomized settings. We present problems which are uniformly weakly tractable, but not quasi-polynomially tractable. There are also problems that are weakly tractable, but not uniformly weakly tractable. This shows that the notion of uniform weak tractability does not, in general, coincide with the notions of weak or quasi-polynomial tractability.
Journal: Journal of Complexity - Volume 29, Issue 6, December 2013, Pages 438–453