For a system of polynomial equations over Q;p; we present an efficient construction of a single polynomial of quite small degree whose zero set over Q;p; coincides with the zero set over Q;p; of the original system. We also show that the polynomial has some other attractive features such as low additive and straight-line complexity.The proof is based on a link established here between the above problem and some recent number theoretic result about zeros of p-adic forms.

We prove that at least 3k−4/k(2k−3)(n/2) – O(k)equivalence tests and no more than 2/k (n/2) + O(n) equivalence tests are needed in the worst case to identify the equivalence classes with at least k members in set of n elements. The upper bound is an

In this paper we consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x1, x2, ..., x t be variables. Given a matrix M= M(x1, x2, ..., x t ) with entries chosen from E ∪ {x1, x2, ..., x t }, we want to determine $$\max rank_S (M) = \mathop {max}\limits_{(a_1 ,a_2 ,...a_t ) \in S^t } rank M(a_1 ,a_2 ,...a_t )$$ and $$\min rank_S (M) = \mathop {min}\limits_{(a_1 ,a_2 ,...a_t ) \in S^t } rank M(a_1 ,a_2 ,...a_t ).$$There are also variants of these problems that specify more about the structure of M, or instead of asking for the minimum or maximum rank, ask if there is some substitution of the variables that makes the matrix invertible or noninvertible.Depending on E, S, and on which variant is studied, the complexity of these problems can range from polynomial-time solvable to random polynomial-time solvable to NP-complete to PSPACE-solvable to unsolvable.

Let M be a fixed finite monoid.We consider the problem of implementing a data type containing a vector x ϭ ( x 1 , x 2 , . . ., x n ) ʦ M n , initially (1, 1, . . ., 1), with two kinds of operations, for each i ʦ {1, . . ., n} and a ʦ M, an operation change i,a which changes x i to a and a single operation product returning ͟ iϭ1 n x i .This is the dynamic word problem for M. If we in addition for each j ʦ {1, . . ., n} have an operation prefix j returning ͟ iϭ1 j x i , we get the dynamic prefix problem for M. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits.We obtain a partial classification of the complexity based on algebraic properties of M.

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x=(x/sub 1/,x/sub 2/,...,x/sub n/)/spl isin/M/sup n/, initially (1,1,...,1) with two kinds of operations, for each i/spl isin/{1,...,n}, a/spl isin/M, an operation change/sub i,a/ which changes x/sub i/ to a and a single operation product returning /spl Pi//sub i=1//sup n/x/sub i/. This is the dynamic word problem. If we in addition for each j/spl isin/{1,...,n} have an operation prefix/sub j/ returning /spl Pi//sub i=1//sup j/x/sub i/, we talk about the dynamic prefix problem. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a classification of the complexity based on algebraic properties of M.>