关于若干函数类的多项式时间谱系(Ⅰ)

对计数函数类#P,Span-P和最优化函数类Opt-P及FΔ₂^P进行了推广,给出了4个关于函数的多项式时间谱系,证明了关于最优化函数的多项式时间谱系,与Krentel定义的谱系是相同的,讨论了这些谱系自身以及谱系之间的关系。     

线性分式规划问题的多项式时间近似算法

本文针对线性比式和分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.     

多供应商多零售商下经济批量问题的多项式时间算法研究

基于多供应商和多零售商构成的经济批量问题,通过构建优化模型,分析了订购费用为全部单位数量折扣和增加数量折扣两种情形模型最优解的相关性质。将这些性质应用到动态规划算法设计中,对订购费用为全部单位数量折扣时的一种特殊情形及增加数量折扣的一般情形分别设计了求解问题最优解的多项式时间算法,并用算例说明了算法的执行过程和有效性。     

线性分式多乘积规划问题的多项式时间近似算法

本文首先将一般形式的线性分式多乘积规划问题(MP),转化为特殊形式的子问题.再根据子问题提出一种求解(MP)的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.     

关于多项式函数的计数

Polynomial functions （in particular, permutation polynomials） play an important role in the design of modern cryptosystem. In this note the problem of counting the number of polynomial functions over finite commutative rings is discussed. Let A be a general finite commutative local ring. Under a certain condition, the counting formula of the number of polynomial functions over A is obtained. Before this paper, some results over special finite commutative rings were obtained by many authors.     

多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

在经典排序论中，一般都作以下两条假设：其一是每台机器在任一时刻至多加工一个零件，其二是每个零件在任一时刻至多被一台机器加工．在这篇文章中，研究多台机器可同时加工一个零件的多机排序问题，且每个零件可在固定的一个机器的子集上加工．本文在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究了这种问题的计算复杂性．     

单台机以总完工时间为目标的批排序问题

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.     

关于复杂性类的限制相对化

研究了复杂性类的两种类型的限制相对化:限制访问Oracle的查询次数和限制访问Oracle的类型.提出了Few算子和强Few算子并利用Few算子和强Few算子得到了这两种限制相对化的新特征.利用这种新特征给出了一个一般性的时间谱系崩溃结果,它推广、加强了原有的时间谱系崩溃结果.利用这种新特征进一步深刻地研究了概率多项式时间复杂性类PP的能力.     

一个关于多项式函数的因式定理

本文建立了一个极具实用价值的关于多项式函数含有 pxk-q型因式的充分必要条件 .     

关于两类广义多项式的一些恒等式(英文)

By means of generating function and partial derivative methods, we investigate and establish several general summation formulas involving two classes of polynomials. The general results would apply to yield some identities for the Pell polynomials and Pell-Lucas polynomials, and other general polynomials can also be recovered in this paper.     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

关于多项式的Waring问题（Ⅱ）

设ｆ＿ｌ（ｘ）是首项系数为正的ｌ次整系数多项式，满足条件：不存在整数ｄ，ｑ＞１使得ｆ＿ｌ（ｘ）≡ｄ（ｍｏｄｑ）对所有ｘ成立．记Ｒ＿ｋ（ｎ）为方程的正整数的解数，本文的主要结果是：对于及充分大的ｎ，我们有Ｒ＿ｋ（ｎ）》这是Ｖａｕｇｈａｎ关于Ｗａｒｉｎｇ问题的一个结果对多项式的推广。     

关于多项式函数的一个定理

给出了函数f（x）为多项式函数的一个充分必要条件。     

一个具有两类工件的多目标排序的多项式时间算法

本文考虑具有两个工件集的单机排序问题.第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小.本文证明该问题可在O(n1n2(n1 n2))时间内求解.     

NP完全问题多项式时间算法研究

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .     

现代物流技术中装卸工问题的拟多项式时间可解情况

装卸工问题是从现代物流技术中提出的一个实际问题，这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展，促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题，本文研究限制情形下的装卸工问题，并证明是拟多项式时间可解的。     

带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法

讨论Wikum的关于带有延迟时间下界的k-(n1,1,…,1)-链形结构排序问题的拟多项式时间算法,其中当n1=2的情况已由Yin等人(1999)解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出较Yin等人(1999)的算法更加有效的拟多项式时间算法.为了保持文章的连续性,也将列出Yin等人(1999)的n1=2的算法加以比较.     

若干包含Laguerre多项式的等式和同余式

令L_n(x)为Laguerre多项式,即L_0(x)=1,L_1(x)=-x+1,且对所有整数n≥1,有递推公式L_(n+1)(x)=(2n+1-x)L_n(x)-n~2L_(n-1)(x).主要使用组合及初等方法研究一类包含L_n(x)的卷积和式,给出其有趣的计算公式,并得到一些包含Laguerre多项式的等式和同余式,这些结果均有着重要的应用.     

巴拿赫空间中线性离散时间系统的多项式二分性

本文给出了巴拿赫空间中线性差分方程的两个多项式二分性概念, 使其在相应空间中的范数的增长速度不快于指数型增长. 并用实例阐释了相关概念之间的关系. 借助于指数二分性的研究方法讨论了多项式二分性的特征, 所得结论推广了指数稳定性及指数二分性中的一些已有结果.