Complexity of Deciding Solvability of Polynomial Equations over p-adic Integers

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. St. Petersburg Institute for Informatics and Automation of the Academy of Sciences of Russia, 14th line 39, St. Petersburg 199178, Russia and Department of Computer Science, University of Bonn, 53117 Bonn. Research supported by the Volkswagen--Stiftung, Program on Computational Complexity. y Department of Computer Science, University of Bonn, 53117 Bonn and International Computer Science Institute, Berkeley, Californ..