We study the complexity of computing the sign of the Tutte polynomial of a
graph. As there are only three possible outcomes (positive, negative, and
zero), this seems at first sight more like a decision problem than a counting
problem. Surprisingly, however, there are large regions of the parameter space
for which computing the sign of the Tutte polynomial is actually #P-hard. As a
trivial consequence, approximating the polynomial is also #P-hard in this case.
Thus, approximately evaluating the Tutte polynomial in these regions is as hard
as exactly counting the satisfying assignments to a CNF Boolean formula. For
most other points in the parameter space, we show that computing the sign of
the polynomial is in FP, whereas approximating the polynomial can be done in
polynomial time with an NP oracle. As a special case, we completely resolve the
complexity of computing the sign of the chromatic polynomial - this is easily
computable at q=2 and when q is less than or equal to 32/27, and is NP-hard to
compute for all other values of the parameter q.