
University of Bonn > Department of Computer Science > Chair V  
CSReports 1997  Copyright 1997 University of Bonn, Department of Computer Science, Abt. V  
85183

Complexity of Deciding Solvability of Polynomial Equations over padic Integers
Alexander Chistov, Marek Karpinski [Download PostScript] [Download PDF] Consider a system of polynomial equations in $n$ variables of degrees less than $d$ with integer coefficients with the lengths less than $M$. We show using the construction close to smooth stratification of algebraic varieties that an integer \[\Delta < 2^{Md^{2^{n(1+o(1))}}}\] corresponds to these polynomials such that for every prime $p$ the considered system has a solution in the ring of $p$adic numbers if and only if it has a solution modulo $p^N$ for the least integer $N$ such that $p^N$ does not divide $\Delta$. This improves the previously known result by B.~J.~Birch and K.~McCann. 

Last Change:
02/04/15 at 12:54:06
Deutsch 
University of Bonn > Department of Computer Science > Chair V 