  We show factorization of polynomials in one variable over the tropical
semiring is in general NP-complete, either if all coefficients are finite, or
if all are either 0 or infinity (Boolean case). We give algorithms for the
factorization problem which are not polynomial time in the degree, but are
polynomial time for polynomials of fixed degree. For two-variable polynomials
we derive an irreducibility criterion which is almost always satisfied, even
for fixed degree, and is polynomial time in the degree. We prove there are
unique least common multiples of tropical polynomials, but not unique greatest
common divisors. We show that if two polynomials in one variable have a common
tropical factor, then their eliminant matrix is singular in the tropical sense.
We prove the problem of determining tropical rank is NP-hard.
