Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1997 Copyright 1997 University of Bonn, Department of Computer Science, Abt. V
85183

Complexity of Deciding Solvability of Polynomial Equations over p-adic 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