dc.description.abstract | An ultrametric field is a field that is locally compact as a metric space with
respect to a non-archimedean absolute value. The main topic of this dissertation is
to study roots of polynomials over such fields.
If we have a univariate polynomial with coefficients in an ultrametric field and
non-vanishing discriminant, then there is a bijection between the set of roots of the
polynomial and classes of roots of the same polynomial in a finite ring. As a consequence,
there is a ball in the polynomial space where all polynomials in it have the
same number of roots.
If a univariate polynomial satisfies certain generic conditions, then we can efficiently
compute the exact number of roots in the field. We do that by using Hensel's
lemma and some properties of Newton's polygon.
In the multivariate case, if we have a square system of polynomials, we consider
the tropical set which is the intersection of the tropical varieties of its polynomials.
The tropical set contains the set of valuations of the roots, and for every point in
the tropical set, there is a corresponding system of lower polynomials. If the system
satisfies some generic conditions, then for each point w in the tropical set the number
of roots of valuation w equals the number roots of valuation w of the lower system.
The last result enables us to compute the exact number of roots of a polynomial
system where the tropical set is finite and the lower system consists of binomials.
This algorithmic method can be performed in polynomial-time if we fix the number of variables.
We conclude the dissertation with a discussion of the feasibility problem. We
consider the problem of the p-adic feasibility of polynomials with integral coefficients
with the prime number p as a part of the input. We prove this problem can be solved
in nondeterministic polynomial-time. Furthermore, we show that any problem, which
can be solved in nondeterministic polynomial-time, can be reduced to this feasibility
problem in randomized polynomial-time. | en |