In this paper, we study the computational complexity of sets of different densities in NP. We show that the deterministic computation time for sets in NP can depend on their density if and only if there is a collapse or partial collapse of the corresponding higher nondeterministic and deterministic time bonded complexity classes. We show also that for NP sets of different densities there exist complete sets of the corresponding density under polynomial time Turing reductions. Finally, we show that these results can be interpreted as results about the complexity of theorem proving and proof presentation in axiomatized mathematical systems. This interpretation relates fundamental questions about the complexity of our intellectual tools to basic structural problems about P, NP, CoNP, and PSPACE, discussed in this paper.