On Drinfeld's universal formal group over thep-adic upper half plane

Conclusion All of our results are stated for 2-dimensional modules with action by the quaternion division algebra overQ _p . Drinfeld's results are true in much greater generality. We remark that our results generalize easily to the case of 2-dimensional modules with action by quaternion algebras over extensions ofQ _p by applying the theory of formal -modules. We suspect that Drinfeld's higher dimensional modules over are determined by formulae similar to that in Theorem 46, but with and generalized to moduli for higher dimensionalQ _p -subspaces of ; however, we have not investigated this in any detail.Although this work amplifies Drinfeld's original paper by supplying many details in certain cases, it is seriously limited in that it considers lifts of SFD modules to unramified rings only. The most interesting points in thep-adic upper half plane are the points defined over ramified rings, which reduce modp to the singular points on the special fiber. What happens there? We do not have a simple answer.Drinfeld's moduli for formal groups on thep-adic upper half plane is the basis for his proof that Shimura curves havep-adic uniformizations. In a later work, we hope to exploit improved versions of the techniques in this work to better understand the arithmetic of Shimura curves. In particular, in the course of work onp-adicL-functions, we have been led to construct certain p-adic periods associated to the cohomology of sheaves on Shimura curves which depend essentially on the existence of ap-adic uniformization. We hope to use Drinfeld's moduli to obtain a more natural construction of these periods in terms of the Gauss-Manin connection, and thereby to gain a better understanding of how they might come to appear in special values ofp-adicL-functions.This research was partially supported by an NSF Postdoctoral Fellowship     

Computational Complexity in Algebraic Systems

Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.     

The Computational Complexity of Extrapolation Methods

This paper analyzes the cost of extrapolation methods for non-stiff ordinary differential equations depending on the number of digits of accuracy requested. Extrapolation of the explicit midpoint rule is applied for various number sequences. We show that for sequences with arithmetic growth, the cost of the method is polynomial in the number of digits of accuracy, while for sequences of numbers with geometric growth, the cost is super-polynomial with respect to the same parameter.     

Computational Complexity of Checking Identities in 0-Simple Semigroups and Matrix Semigroups over Finite Fields

In this paper we analyze the so-called word problem for (finite) combinatorial 0-simple semigroups and matrix semigroups from the viewpoint of computational complexity.     

广义m阶Bernoulli数和广义m阶Euler数的计算公式

使用发生函数方法,利用第一类Stirling数和第二类Stirling数分别给出广义m阶Bernoulli数和广义m阶Euler数的计算公式.     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Reductions in Computational Complexity Using Clifford Algebras

A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λ^k, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.     

On the Computational Complexity of a Rigidity Problem

Consider a structure of flexible joints connected by rigid bars.These bars will constrain the possible motions of the jointsof this structure. By "pinning down" some of the joints so thatthey cannot move further constraints will be added. In thisway the entire structure can be made rigid. A problem consideredby Bolker & Crapo (1977) and others, is that of findingthe minimum number of joints that must be pinned in order tomake a given two- or three-dimensional structure rigid. We considerthe computational complexity of this problem. Lovasz (1980)gives a somewhat complicated but polynomial time procedure forthis problem in the two-dimensional case. In this paper we showthat in three or more dimensions the problem is NP-complete,and so is unlikely to have a polynomial time algorithm.     

Computational Complexity of Fixed Points and Intersection Points

We study the computational complexity of Brouwer′s fixed point theorem and the intersection point theorem in the two-dimensional case. Papadimitriou (1990, in "Proceedings, 31st IEEE Sympos. Found. Comput. Sci.," pp. 794-801) defined a complexity class PDLF to characterize the complexity of the fixed point theorem in the three-dimensional case. We define a subclass PMLF of PDLF and show that the fixed points and the intersection points of polynomial-time computable functions are not polynomial-time computable if PMLF contains a function on unary inputs that is not polynomial-time computable.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

There Exists a Problem Whose Computational Complexity Is Any Given Function of the Information Complexity

We present an information-based complexity problem for which the computational complexity can be any given increasing function of the information complexity, and the information complexity can be any non-decreasing function of ϵ⁻¹, where ϵ is the error parameter.     

Complexity of optimizing over the integers

Mathematical Programming - In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete...     

Forcing Linearity Numbers for Modules over PID's

Let V be a module over a principal ideal domain. Then V = M N where M is divisible and N has no nonzero divisible submodules. In this paper we determine the forcing linearity number for V when N is a direct sum of cyclic modules. As a consequence, the forcing linearity numbers of several classes of Abelian groups are obtained.