## Abstract

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem S=^{Sd} in the average case setting to be weakly tractable but not polynomially tractable. As a result of the tensor product structure, the eigenvalues of the covariance operator of the induced measure in the one-dimensional problem characterize the complexity of approximating S_{d} d≥1, with accuracy ε. If ∑j=j=1 ^{∞}λ_{j} ≥ 1 and λ_{2} > 0, we know that S is not polynomially tractable iff lim sup _{j→∞}λ_{j}j^{p} =∞ for all p > 1. Thus we settle the open problem by showing that S is weakly tractable iff ∑_{j>n} λ_{j}=o(ln^{-2}n). In particular, assume that ℓ=lim/j→∞^{λj}jln ^{3}(j+1), exists. Then S is weakly tractable iff ℓ = 0.

Original language | English (US) |
---|---|

Pages (from-to) | 273-280 |

Number of pages | 8 |

Journal | Journal of Complexity |

Volume | 27 |

Issue number | 3-4 |

DOIs | |

State | Published - 2011 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- General Mathematics
- Control and Optimization
- Applied Mathematics

## Keywords

- Complexity
- Multivariate problem
- Tractability