A new criterion for tractability of multivariate problems

Tractability of multivariate problems studies their complexity with respect to the number of variables, dd, and the accuracy of the solution εε. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy.We introduce two new tractability types, polylog tractability and lnκlnκ-weak tractability. A problem is polylog tractable iff its complexity is polynomial in dd and in lnε−1lnε−1, while a problem is lnκlnκ-weakly tractable iff its complexity is not exponential in dd and lnκε−1lnκε−1, for some κ≥1κ≥1. We study general multivariate problems and multivariate tensor product problems. We provide necessary and sufficient conditions for the respective tractability types. Moreover, we show that a multivariate tensor product problem cannot be polylog tractable and cannot be ln1ln1-weakly tractable (i.e., with κ=1κ=1) unless it is trivial.