结构多顶式复杂性研究中使用的一些方法

本文介绍了结构多项式性研究中用的一些方法，包括能行对角线方法，能行有穷延伸法，填料法，间隙法，延迟对角线法，加速法。     

推广的Kantorovich多项式的一些基本性质

本文对推广的Bernstein-Kantorovich多项式进行了深入地研究和讨论,给出并证明了一些重要的基本性质.     

一个求解水平线性互补问题的高阶可行内点算法的多项式复杂性

最近,Zhao和Sun提出了一个求解sufficient线性互补问题的高阶不可行内点算法.不需要严格互补解条件,他们的算法获得了高阶局部收敛率,但他们的文章没有报告多项式复杂性结果.本文我们考虑他们所给算法的一个简化版本,即考虑求解单调水平线性互补问题的一个高阶可行内点算法.我们证明了算法的迭代复杂性是     

使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).     

一类Toeplitz线性方程组与多项式除法的复杂性

本文给出带状Toeplitz线性方程组,带状三角Toeplitz线性方程组求解的快速方法,其方法基于三角Toeplitz方程与Toeplitz方程的快速求解.并由此给出了一般多次式除法的新算法.     

关于微分多项式的一些结果

设ｆ是平面内超越亚纯函数，满足Ｎ（ｒ，ｆ）＝Ｓ（ｒ，ｆ）．Ｐ［ｆ］是ｆ的多项式，Ｑ［ｆ］是ｆ的微分多项式。本文考虑了形如Ｐ［ｆ］ｆ＇＋Ｑ［ｆ］（特殊情形为ｆ￣ｎｆ＇＋Ｑ［ｆ］及Ｐ［ｆ］ｆ＇－Ｃ，Ｃ为常数）的微分多项式的值分布，推广并改进了Ｗ．Ｋ．Ｈａｙｍａｎ，Ｊ．Ｃｌｕｎｉｅ，Ｅ．Ｍｕｅｓ等人关于整函数的一些结果。     

Morgan-Voyce多项式的一些新性质

本文证明了Morgan-Voyce多项式的零点在闭区间$[-4,0]$上是稠密的.本文也证明了Morgan-Voyce多项式系数的分布是渐近正态的,以及它的系数矩阵是全正的.     

单纯形上Bernstein多项式的一些性质

设Ｂ_m（ｆ，·）为函数ｆ在ｄ维单纯形σ上的ｎ阶Ｂｅｒｎｓｔｅｉｎ多项式，本文对ｆ∈Ｃ^ｒ（σ）及ｆ∈Ｃ^r+2（σ）给出了ｆ的各阶编导数用Ｂ_n（ｆ，·）相应偏导数逼近的误差估计．同时也考虑了整系数Ｂｅｒｎｓｔｅｉｎ多项式的Ｌ_p模估计     

关于Bernoulli-Goss多项式的一些注记

Goss和冯克勤证明了:对q≥2,F_q[T]中存在无穷多不正规的不可约多项式。Ireland和Small给出了第n个Bernoulli-Goss多项式(1≤n≤p²—1)的明确表达式,利用这个结果,他们对于3≤p≤269求出所有形为T²—a(a∈F_P[T])的正规二次不可约多项式。本文对n有两项q-adic展开的情形,给出F_q[T]中第n个Bernoulli-Goss多项式的明确表达式。由此证明了:对任意q≥3,F_q[T]中存在无穷多不可约多项式同时是第一类和第二类不正规的,我们还给出二次不可约多项式正规性的一些等价条件。基于文献[3]中的计算结果,我们决定出特征不超过269的所有F_q[T]中二次正规不可约多项式。     

About Segment Complexity of Turing Reductions

We apply complexity concepts to define a new sort of sub-Turing reducibilities ≤ ?? make the degree hierarchy thinner and to obtain some new specifications of the well known jump inversion theorem of Friedberg. We show that this theorem doesn't hold when ≤ T is replaced with ≤ ??, where ?? is any countable subset of the class ?? of all total increasing functions f : ? → ?.     

Some Complexity Results for Polynomial Ideals

In this paper, we survey some of our new results on the complexity of a number of problems related to polynomial ideals. We consider multivariate polynomials over some ring, like the integers or the rationals. For instance, a polynomial ideal membership problem is a (w+ 1)-tupleP= (f,g₁,g₂, …g_wwherefand theg_iare multivariate polynomials, and the problem is to determine whetherfis in the ideal generated by theg_i. For polynomials over the integers or rationals, this problem is known to be exponential space complete. We discuss further complexity results for problems related to polynomial ideals, like the word and subword problems for commutative semigroups, a quantitative version of Hilbert's Nullstellensatz in a complexity theoretic version, and problems concerning the computation of reduced polynomials and Gröbner bases.     

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

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

Polynomial Computability of Certain Rudimentary Predicates

The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form . Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.     

求矩阵最小多项式的初等变换方法

分别给出计算矩阵的最小多项式和向量关于矩阵的最小多项式的初等变换方法 .     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

The Complexity of Self-Regular Proximity Based Infeasible IPMs

Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. In this paper a self-regular proximity based Infeasible Interior Point Method (IIPM) is proposed for linear optimization problems. First we mention some interesting properties of a specific self-regular proximity function, studied recently by Peng and Terlaky, and use it to define infeasible neighborhoods. These simple but interesting properties of the proximity function indicate that, when the current iterate is in a large neighborhood of the central path, large-update IIPMs emerge as the only natural choice. Then, we apply these results to design a specific self-regularity based dynamic large-update IIPM in large neighborhood. The new dynamic IIPM always takes large-updates and does not utilize any inner iteration to get centered. An worst-case iteration bound of the algorithm is established. Finally, we report the main results of our computational experiments.     

Polynomial Crystallographic Actions on the Plane

We study polynomial crystallographic actions on the plane. These are properly discontinuous and cocompact actions, which are expressed by polynomial functions. We prove that any such action of a polycyclic-by-finite group is of bounded degree and conversely that any polynomial crystallographic action of bounded degree comes from a polycyclic-by-finite group. This last result is a generalization of the well known Auslander conjecture.     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.