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

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