Estimation of software reliability according to random testing is of particular importance in software reliability engineering. The author proposes a method for software reliability estimation in this paper. It reckons the complexity of the computation as an important factor of reliability estimation so that software is not considered as a black-box. It uses the pseudo-dimension of software neighbourhood as a measure of software complexity. Therefore, it can be used to estimate software reliability according to fault-based random testing. The author also proves some relationships between computational complexity and the pseudo-dimension of the set of functions that can be computed within the complexity bound.