Preprint 2/2006

Generalized Tractability for Multivariate Problems

Michael Gnewuch and Henryk Woźniakowski

Contact the author: Please use for correspondence this email.
Submission date: 09. Jan. 2006
Pages: 47
published in: Journal of complexity, 23 (2007) 2, p. 262-295 
DOI number (of the published article): 10.1016/j.jco.2006.06.006
Bibtex
with the following different title: Generalized tractability for multivariate problems. Pt. 1 : Linear tensor product problems and linear information
Download full preprint: PDF (375 kB), PS ziped (262 kB)

Abstract:
There are many papers studying polynomial tractability for multivariate problems. Polynomial tractability means that the minimal number formula27 of information evaluations needed to reduce the initial error by a factor of formula29 for a multivariate problem defined on a space of d-variate functions may be bounded by a polynomial in formula33 and d and this holds for all formula37.

We propose to study generalized tractability by verifying when formula27 can be bounded by a power of formula41 for all formula43, where formula45 can be a proper subset of formula47. Here T is a tractability function which is non-decreasing in both variables and grows slower than exponentially to infinity. In this paper we study the set formula51 for some formula53 and formula55. We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on T such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does hold.

04.01.2023, 02:13