  The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that
encodes many interesting properties of the graph. We study the complexity of
the following problem, for rationals x and y: take as input a graph G, and
output a value which is a good approximation to T(G;x,y). Jaeger, Vertigan and
Welsh have completely mapped the complexity of exactly computing the Tutte
polynomial. They have shown that this is #P-hard, except along the hyperbola
(x-1)(y-1)=1 and at four special points. We are interested in determining for
which points (x,y) there is a "fully polynomial randomised approximation
scheme" (FPRAS) for T(G;x,y). Under the assumption RP is not equal to NP, we
prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes
x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two
exceptions to this result are the half-line x<-1, y=1 (which is still open) and
the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show
to be equivalent in difficulty to approximately counting perfect matchings. We
give further intractability results for (x,y) in the vicinity of the origin. A
corollary of our results is that, under the assumption RP is not equal to NP,
there is no FPRAS at the point (x,y)=(0,1--lambda) when \lambda>2 is a positive
integer. Thus there is no FPRAS for counting nowhere-zero \lambda flows for
\lambda>2. This is an interesting consequence of our work since the
corresponding decision problem is in P for example for \lambda=6.
