A simple polyhedron is called special if each of its 1-dimensional strata is an open 1-cell, and each of its 2-components is an open 2-cell. Generalizing the classical concept of a 3-manifold, Matveev introduced the concept of a virtual 3-manifold, which is an equivalence class of special polyhedra. Many important properties and invariants of 3-manifolds have been extended to virtual manifolds. The complexity of a manifold is an important invariant in the theory of 3-manifolds. In this article, the authors introduce a notion of complexity for a virtual 3-manifold. More precisely, they investigate the values of the complexity for virtual manifolds presented by special polyhedra with one or two 2-components. On the basis of these results they establish the exact values of the complexity for a wide class of hyperbolic 3-manifolds with totally geodesic boundary.