1) Polynomial-time Hierarchy
多项式时间谱系PH
2) time polynomial
时间多项式
1.
To solve filtering divergence,the Unscented Kalman filter (UKF) algorithm,which has better non-linear approximation ability,is adopted; on the other hand,a set of time polynomials is constructed based on the observation values from radar and infrared,and after radar is turned off,the target motion states are estimated by this set of polynomials.
为了改善纯角度跟踪的滤波发散问题,一方面,在滤波处理时采用了非线性逼近能力更强的U nscented卡尔曼滤波算法;另一方面,充分利用雷达、红外同时开机时的量测信息,构造出一组时间多项式,在雷达关机期间,利用该组时间多项式估计目标的运动状态,辅助红外传感器进行跟踪。
3) polynomial time
多项式时间
1.
A algorithm with central line neighbour hood of polynomial time for linear programming is given.
算法具有多项式时间收敛性 ,总迭代次数为 O(n
4) polynomial-time algorithm
多项式时间算法
1.
In this paper,we gave two polynomial-time algorithms for solving two special unit type shortest path improvement problems under Hamming distance in single-source arborescence,and we studied some properties of the general problem.
给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质。
2.
Finally a polynomial-time algorithm for the optimal strategy of OEM is gotten by using dual theory of bilevel programming.
最后,利用双层规划的对偶理论,给出求解OEM业务最优策略的一种多项式时间算法。
3.
It is shown that this algorithm is a polynomial-time algorithm which can algorithm can find anε-approximate solution in O(n~(1/2)lnε~(-1)) iterations.
给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法。
5) polynomial time algorithm
多项式时间算法
1.
A polynomial time algorithm for the scheduling problem of identical coupled-task jobs is presented in.
本文讨论并给出了由n个相同的耦合工件构成的耦合工件组作业问题的多项式时间算法。
2.
To present a new polynomial time algorithm for China traveling salesman problem, first, point set was partitioned into a number of subpoint sets by using convex hull and medial axis.
研究求解中国货郎担问题最短回路的多项式时间算法。
3.
In this paper,we will prove that there exit an orthogonal matching decomposition of M in simple bipartite graph,and present a polynomial time algorithm of this decomposition.
在本文中我们将证明对于简单二部图G,存在关于完美匹配M的正交匹配分解,并给出了求这个分解的多项式时间算法。
补充资料：多项式谱系
多项式谱系
polynomial hierarchy
dUoxiQngshi Puxi多项式谱系(polynomi目hie州”℃hy)递归论中克林算术谱系的多项式变形，很多似乎不在NP类中的计算问题属于多项式谱系的某一层次。多项式谱系的基本思想是R.K田甲于1972年提出的，A.Me界r和L.Stockmeyer在1973年给出了多项式谱系的严格形式化定义。 基于多项式时间图灵归约和多项式时间非确定图灵归约的概念，可建立P和NP类关于任何语言L的相对化定义，它们分别记为P(L)和NP(L)，有 P(L)二{厂互艺‘}I.’簇弘} NP(L)={L’g刃’1L’簇岁L{这种对P和NP类关于语言的相对化概念，可自然地推广到任何语言类留上: P(昭)二UP(L)，NP(节)二U NP(L) L任CL任嘴基于这种定义，可将P和NP视为语言类上的一种算子，且有蜒二P(留)二NP(留)，P(P)=P，NP(P)=NP，从自语言类P开始，将算子NP重复地作用在其上，便产生一个语言类的无穷递增序列:P，Np，Np(NP)，NP(Nl〕(Nl〕))，…它们依次记为写，写，成，写，…，也即 写二P，聪1=N’P(军)，k)o 另外，还可定义两类与写相关的复杂性类可和乙f: 可=c。一军={L里乏‘】兀〔雾} 乙居=尸，△乐1=尸(写)，k)0这三种复杂性类有下述基本关系: 军里军n可，军U可里。孰由此可见 昌军一昌可一昌△f由军，可及叮(k)0)所描述的层次结构记为PH，并称PH为多项式谱系。 多项式谱系也可如同算术谱系那样，用交替量词的形式来表示。两者之间的区别仅仅是存在量词」y代之以多项式存在量词日与;全称量词Vy代之以多项式规模全称量词V与;递归集(语言)代之以多项式时间可计算语言。这就是C户Wrath司1定理:对于所有k)O (1)L任军当且仅当存在L’任p，使得xeL当且仅当〕今IV勺2…q侠<、，yl，…，yk>〔L。其中当k为偶数时，Q玫为V从;当k为奇数时，奶乍为〕气; (2)L任衅当且仅当存在L’〔P，使得x任L当且仅当V与1日与2…Q恤(x，yl，y:，一，yk>任L‘。其中当k为偶数时Q’yk为3从;当k为奇数时，Q玩为V从。 在wrathall定理中的日勺意指存在多项式尸，对于满足}引钱尸(}x})的某些y任乏’;V与意指存在多项式尸，对于满足}川(尸(}x})的所有y呀召长。 多项式谱系的这种表述形式，对于分析计算问题所处的层次常常更为方便。
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条