In the probabilistic network considered in this paper, the edges are perfectly reliable but the nodes fail with some known probability. The node failure probability distributions are independent and identical. The network is in an operational state if the surviving nodes induce a connected graph. The residual node connectedness reliability R(G) is the probability that the graph induced by the surviving nodes is connected. This measure is different from the widely studied K-terminal network reliability measure. This paper proves that the problem of computing the residual connectedness reliability is NP-hard by showing that the problem of counting the number of node-induced connected subgraphs of a given graph is NP-complete. Results are obtained by methods of mathematical complexity theory and symbolic logic; the esoteric language and notation require an expert reader. Two of the references are unpublished, but this does not seriously reduce the usefulness of the paper, since they are not used in the text to support any of the major conclusions.