论文部分内容阅读
在许多学科中,例如物理学、化学、计算机科学、量子力学、金融学、经济学等,经常会遇到定义在d维多变量函数空间的数值逼近问题,其中d可能很大,成百上千,甚至更大,当d很大的时候,通常在指定的误差ε下,用函数的泛函(线性信息)或函数值(标准信息)作为信息构造算法来逼近该问题.逼近该多变量数值问题算法的复杂性,记为C(n,ε,d),一直是近年来计算数学的主要研究方向之一.逼近该多变量问题算法所需的最少信息个数称为信息的复杂性,记为n(ε,d).显然信息的复杂性是算法复杂性的一个下界,尤其对于许多线性问题,信息的复杂性与算法的复杂性是成一定的比例,所以算法复杂性的研究重点集中于信息的复杂性研究上. 多变量问题的易处理性主要研究n(ε,d)如何依赖于ε和d,传统的多变量问题研究时,对于任给的d是固定的,那么就容易忽略了维数d的影响,而n(ε,d)有可能依赖于d的指数形式增长,所以对于多变量问题的复杂性还需要新的大量的研究.1994年,波兰数学家Wo(z)niakowski教授提出了多变量问题易处理性的许多新慨念与理论,例如,多变量问题的不易处理性(intractability)、强易处理性(strong tractability)、弱易处理性(weak tractability)、多项式易处理性(polynomial tractability)、弱拟多项式易处理性(weak and quasi-polynomial tractability)、对数多项式易处理(polylogtractability),许多学者研究并得出大量成果.本文主要在平均框架下对多变量问题的对数多项式易处理性与弱易处理性做进一步研究. 本文的工作主要包括以下几章: 第一章首先简要介绍信息与算法的复杂性与易处理性相关研究背景和发展历史,给出本文需要的复杂性的一些基本概念和符号以及结果. 第二章主要在平均框架下讨论多变量问题的易处理性,并给出了多变量问题是对数多项式易处理及(s,lnk)弱易处理的充要条件,随后对于特殊的加权逼近问题,证明了加权逼近问题S是lnk弱易处理性,并且在线性信息与标准信息下是等价的. 第三章还是在平均框架下,针对张量积问题进行讨论,首先介绍了基本知识,并给出了张量积问题是(s,t)弱易处理的充要条件,然后证明了线性张量积问题既不是(1,ln1)弱易处理也不是对数多项式易处理的. 第四章对前面几章进行总结,提出自己今后关于进一步研究的工作,并给出了几个自己暂时未解决的问题.