Is the problem of finding the "all-terminal connectivity polynomial" polynomially bounded?
I'll convert my comment to an answer. 

The problem of computing the Rel(G) is #P-Complete (see this paper by Karger), and there's also an FPRAS for 1-Rel(G) (also in the Karger paper). Note that if you could verify whether Rel(G) was less than any fixed number $k$, then you could binary search for an approximate solution for Rel(G) that would run in P-time, which seems a little unlikely.