Is the problem of finding the "all-terminal connectivity polynomial" polynomially bounded? I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is polynomially bounded, i.e $|y| &lt; p(|x|)$. 
In this case I guess that $|x| \text{~} n^2$
but I am not sure about $|y|$ .

Note - Definition
For a given graph $G(V, E)$ each edge $E_{ij}$ has a $p_{ij}$-probability of being reliable and $(1 - p_{ij})$ probability of failure. Considering that each edge fails independently and nodes are perfectly reliable, the function

$Rel(G)$ = $Pr[$ for each pair of nodes $x_{i}$ and $x_{j}$ there exists at least one reliable path between them $]$ 

is called all-terminal connectivity (or reliability) function of the network.
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.