$\mathbf{\pmb{(\ln}^s d, \pmb{\ln}^t \epsilon^{\pmb{-}1}\pmb{)}}$-Weak Tractability

Abstract

Tractability studies the complexity of multivariate problems with respect to the accuracy $\epsilon$ and the dimension $d$ (number of variables) of the problem. Much research has gone into studying different tractability criteria, each of which uniquely defines a class of problems that satisfy the criterion. Two classic, prevalent notions are polynomial tractability and weak tractability. None of these criteria, however, reflect the complexity of problems with respect to both the number of bits in the dimension and the number of bits in the accuracy. Therefore, I propose the criterion $(\ln^s d, \ln^t \epsilon^{-1})$-weak tractability for some constants $s,t > 0$. A problem is $(\ln^s d, \ln^t \epsilon^{-1})$-weakly tractable if and only if its complexity is sub-exponential in $\ln^s d$ and $\ln^t \epsilon^{-1}$. I analyze the general case for linear multivariate problems and the specific case of $s=t=1$ for linear tensor product problems and provide theorems describing the necessary and sufficient conditions in each case.