Uniform Families of Polynomial Equations Over a Finite Field and Structures Admitting an Euler Characteristic of Definable Sets

Over a fixed finite field F_p, families of polynomial equations for i = 1,..., k_N, that areuniformly determined by a parameter N, are considered. The notionof a uniform family is defined in terms of first-order logic.A notion of an abstract Euler characteristic is used to givesense to a statement that the system has a solution for infiniteN, and a statement linking the solvability of a linear systemfor infinite N with its solvability for finite N is proved.This characterisation is used to formulate a criterion yieldingdegree lower bounds for various ideal membership proof systems(for example, Nullstellensatz and the polynomial calculus).Further, several results about Euler structures (structureswith an abstract Euler characteristic) are proved, and the caseof fields, in particular, is investigated more closely. 1991Mathematics Subject Classification: primary 03F20, 12L12, 15A06;secondary 03C99, 12E12, 68Q15, 13L05.     

Extrema of a Real Polynomial

In this paper, we investigate critical point and extrema structure of a multivariate real polynomial. We classify critical surfaces of a real polynomial f into three classes: repeated, intersected and primal critical surfaces. These different critical surfaces are defined by some essential factors of f, where an essential factor of f means a polynomial factor of f–c ₀, for some constant c ₀. We show that the degree sum of repeated critical surfaces is at most d–1, where d is the degree of f. When a real polynomial f has only two variables, we give the minimum upper bound for the number of other isolated critical points even when there are nondegenerate critical curves, and the minimum upper bound of isolated local extrema even when there are saddle curves. We show that a normal polynomial has no odd degree essential factors, and all of its even degree essential factors are normal polynomials, up to a sign change. We show that if a normal quartic polynomial f has a normal quadratic essential factor, a global minimum of f can be either easily found, or located within the interior(s) of one or two ellipsoids. We also show that a normal quartic polynomial can have at most one local maximum.     

求三对角矩阵特征多项式一种简便方法

本文通过递推关系 ,直接给出求三对角矩阵特征多项式的一种简便方法 .该方法具有操作简单 ,计算量小的特点 .并给出算例 .     

关于分担多项式的全纯函数的正规族(英文)

In this paper,we study normal families of holomorphic function concerning shared a polynomial.Let F be a family of holomorphic functions in a domain D,k（2）be a positive integer,K be a positive number andα（z）be a polynomial of degree p（p 1）.For each f∈F and z∈D,if f and f sharedα（z）CM and｜f（k）（z）｜K whenever f（z）-α（z）=0 in D, then F is normal in D.     

满足多断点折扣费用函数的经济批量问题的多项式时间算法

在进货费用为全单位数量折扣函数的基础上,建立了一类有限时期内的经济批量问题.通过分析最优解的性质,设计了一个计算复杂性为O(T3+mT2)的动态规划算法,其中m为全单位数量折扣费用中的断点数,T为时期数.最后的算例进一步说明了该算法的有效性.     

Some Polynomial Systems Associated with a Certain Family of Differential Operators

The authors aim at presenting several (presumably new) classes of linear, bilinear, and mixed multilateral generating functions for some general systems of polynomials which are defined by means of a certain family of differential operators. Some of the generating functions considered here are associated with the Stirling numbers of the second kind. Many (known or new) consequences and applications of the results obtained in this paper are also indicated.     

Polynomial expansions of density and distribution functions of scale mixtures

Let Y be an absolutely continuous random variable and W a nonnegative variable independent of Y. It is to be expected that when W is close to 1 in some sense, the distribution of the scale mixture YW will be close to Y. This notion has been investigated by a number of workers, who have provided bounds on the difference between the distribution functions of Y and YW. In this paper we examine the deeper problem of finding asymptotic expansions of the form P(YW ≤ x) = P(Y ≤ x) + Σ_n=1^∞E(W^r ? 1)ⁿG_n(x), where r > 0 and the functions G_n do not depend on W. We approach the problem very generally, and then consider the normal and gamma distributions in greater detail. Our results are applied to obtain better uniform and nonuniform estimates of the difference between the distribution functions of Y and YW.     

The Expected Number of Local Maxima of a Random Algebraic Polynomial

In this work we obtain an asymptotic estimate for the expected number of maxima of the random algebraic polynomial , where a _j (j=0, 1,...,n–1) are independent, normally distributed random variables with mean and variance one. It is shown that for nonzero , the expected number of maxima is asymptotic to log n, when n is large.     

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

Finite problems and the logic of the weak law of excluded middle

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 291–302.Original Russian Text Copyright © 2005 by A. V. Chernov.This revised version was published online in April 2005 with a corrected issue number.     

Reduction of matrices by means of equivalent transformations and similarity transformations

The structure of polynomial matrices in connection with their reducibility by semiscalar-equivalent transformations and similarity transformations to simpler forms is considered. In particular, the canonical form of polynomial matrices without multiple characteristic roots with respect to the above transformations is indicated. This allows one to establish a canonical form with respect to similarity for a certain type of finite collections of numerical matrices. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 769–782, November, 1998.     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000