Negative bias temperature instability (NBTI) has been identified as one of most critical and most pressing degradation issues in nano-scale technologies. Yet most current studies published in literature on NBTI degradation have been limited to either at the device physics level or at the computer architecture level. This paper provides a first in depth study of the NBTI degradation process at the logic level in digital circuits. It demonstrates that the methods used in the existing studies lead to unduly pessimistic results and therefore they must be modified. The paper also compares the effectiveness of some of the known solutions that address NBTI degradation. Several new conclusions are drawn from our study which are important and help identify new research directions that can be taken in view of the more realistic assumptions made in this paper.