Complexity of tropical linear prevarieties and a tropical dual Nullstellensatz

We have shown that the equivalence of two tropical linear
prevarieties has the same complexity as solvability of tropical linear systems (answering a question of V.Voevodsky). While computing the dimension of a tropical
linear prevariety is $NP$-complete.

A direct tropical analogue of the Nullstellensatz is known to be wrong. I've conjectured a tropical dual Nullstellensatz and proved it for univariate polynomials.