关于线性张量积问题拟多项式易处理性的一个注记

A Note on Quasi-polynomial Tractability of Linear Tensor Problems

线性张量积问题的易处理性研究是多元问题易处理性研究的最主要实例。有研究给出了多元问题易处理性的概念,在最坏情形下研究了d维张量积逼近问题,并给出了线性张量积问题具有拟多项式易处理性的一个充要条件。但其证明涉及了T易处理性的很多难以检验的性质。因此应用了线性张量积问题的信息复杂性估计式和一般线性问题具有拟多项式易处理性的一个具体量化表达式,对其充要条件给出了一个极其简单直观的证明。

The tractability of linear tensor product problems is the most important example of multivariate problems tractable re search. Recently, the concept of tractability of multivariate problems has been introduced by somebody; it also studies d-variate ap- proximation problems in the worst case setting, and gives the necessary and sufficient conditions of quasi-polynomiao tractability of linear tensor product problems. But the proof involves lots of nature of T tractability which is difficult to test, so it is difficult to understand. In this paper, we give a very simple and intuitive proof of the necessary and sufficient conditions by using the information complexity estimation formula of linear tensor product problems which and a specific quantitative expression of general linear prob lem which have quaspolynomiao tractability.