Admissible closures of polynomial time computable arithmetic

We propose two admissible closures ${\mathbb{A}({\sf PTCA})}$ and ${\mathbb{A}({\sf PHCA})}$ of Ferreira??s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) ${\mathbb{A}({\sf PTCA})}$ is conservative over PTCA with respect to ${\forall\exists\Sigma^b_1}$ sentences, and (ii) ${\mathbb{A}({\sf PHCA})}$ is conservative over full bounded arithmetic PHCA for ${\forall\exists\Sigma^b_{\infty}}$ sentences. This yields that (i) the ${\Sigma^b_1}$ definable functions of ${\mathbb{A}({\sf PTCA})}$ are the polytime functions, and (ii) the ${\Sigma^b_{\infty}}$ definable functions of ${\mathbb{A}({\sf PHCA})}$ are the functions in the polynomial time hierarchy.     

Index sets of computable structures

The index set of a computable structure is the set of indices for computable copies of . We determine complexity of the index sets of various mathematically interesting structures including different finite structures, ℚ-vector spaces, Archimedean real-closed ordered fields, reduced Abelian p-groups of length less than ω², and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be m-complete Π _n ⁰ , d-Σ _n ⁰ , or Σ _n ⁰ , for various n. In each case the calculation involves finding an optimal sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable Π_n, d-Σ_n, or Σ_n) yields a bound on the complexity of the index set. Whenever we show m-completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey’s theory. Supported by the NSF grants DMS-0139626 and DMS-0353748. Supported by the NSF grant DMS-0502499 and by the Columbian Research Fellowship of the George Washington University. Supported by the NSF grant DMS-0353748. __________ Translated from Algebra i Logika, Vol. 45, No. 5, pp. 538–574, September–October, 2006.     

Elementary explicit types and polynomial time operations

This paper studies systems of explicit mathematics as introduced by Feferman [9, 11]. In particular, we propose weak explicit type systems with a restricted form of elementary comprehension whose provably terminating operations coincide with the functions on binary words that are computable in polynomial time. The systems considered are natural extensions of the first‐order applicative theories introduced in Strahm [19, 20] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on separation of algebraic sets and the ?ojasiewicz exponent for polynomial mappings

In the paper a global separation problem for affine algebraic sets is considered. As application an upper bound for the distance of the graph of polynomial mapping to its zero set in the form of a ?ojasiewicz inequality is given.     

Categories of algebraic sets

The category of algebraic sets is defined in a straightforward way for any algebraic theory . It is a concrete, complete and cocomplete category dually equivalent to a full reflective subcategory of the category of -algebras. For the algebraic theory of commutative algebras over a field K, we get the algebraic sets over K.     

On polynomial sets of classS k,and sets of rankk

Summary Al-Salam and Verma introduced the class S^k of polynomial sets, and characterized such sets by their generating functions. Here we define a class V^k of sets of rank k by means of recurrence relations, and show that S^k ⊂ V^k; and we characterize those sets of S^k, and of V^k, that are orthogonal. Entrata in Redazione il 24 giugno 1977.     

The polynomial topological complexity of Fatou-Julia sets

We analyze the polynomial topological complexity of Fatou-Julia sets, and show that for Sullivan domains of such sets the complexity is equal to 1 in the case of attracting, superattracting and Siegel domains, while for parabolic domains it is greater than 1. Communicated by S.L. Lee     

The polynomial topological complexity of Fatou-Julia sets

We analyze the polynomial topological complexity of Fatou-Julia sets, and show that for Sullivan domains of such sets the complexity is equal to 1 in the case of attracting, superattracting and Siegel domains, while for parabolic domains it is greater than 1.     

A term rewriting characterization of the functions computable in polynomial space

We give a term rewriting characterization of the polyspace functions. Our work follows investigations on term rewriting characterizations of some classes of (sub-) recursive functions as initiated by Cichon and Weiermann [4] and continued by Beckmann and Weiermann [1]. The main novelty of this paper is a technique for reformulating recursion schemes. The aim of this technique is to provide rewriting rules which give rise to rewriting chains whose terms are suitably bounded. This bounding is crucial when dealing with computational classes with space constraints. Received: 14 December 1998 / Published online: 12 December 2001     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

The number of nonequivalent computable indexations for a fixed family of sets

Translated fromAlgebra i Logika, Vol. 32, No. 1, pp. 34–44, January–February, 1993.     

Multivariate polynomial perturbations of algebraic equations

In this note we study multivariate perturbations of algebraic equations. In general, it is not possible to represent the perturbed solution as a Puiseux-type power series in a connected neighborhood. For the case of two perturbation parameters we provide a sufficient condition that guarantees such a representation. Then, we extend this result to the case of more than two perturbation parameters. We motivate our study by the perturbation analysis of a weighted random walk on the Web Graph. In an instance of the latter the stationary distribution of the weighted random walk, the so-called Weighted PageRank, may depend on two (or more) perturbation parameters in a manner that illustrates our theoretical development.     

Numerical solutions of index-1 differential algebraic equations can be computed in polynomial time

The cost of solving an initial value problem for index-1 differential algebraic equations to accuracy ɛ is polynomial in ln(1/ɛ). This cost is obtained for an algorithm based on the Taylor series method for solving differential algebraic equations developed by Pryce. This result extends a recent result by Corless for solutions of ordinary differential equations. The results of the standard theory of information-based complexity give exponential cost for solving ordinary differential equations, being based on a different model.     

Classification of the isomorphic types of martingale-H 1 spaces

LetF _n be an increasing sequence of finite fields on a probability space (Ω,F _n,P) whereF denotes the σ-algebra generated by ∪F _n. ThenF _n is isomorphic to one of the following spaces:H ¹(δ), ΣH _n ¹ ,l ^l.     

Homotopy properties of algebraic sets

In this paper there are announced several homotopy theorems on algebraic subsets of complex projective spaces. Some of the theorems generalize and refine results of the preceding note of the author (RZhMat, 1978, 5A531). It is also asserted that any -dimensional complex affine algebraic set has the homotopy type of a finite -dimensional cellular space. A generalization is given, in two versions, of a theorem of Bart-Larsen (RZhMat, 1973, 7A587).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 83, pp. 67–72, 1979.     

多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.