In view of the low accuracy of the existing nuclear magnetic-resonance (NMR) logging permeability model in tight sandstone reservoirs, we derive a relationship between the NMR spectrum and permeability based on the transverse relaxation theory of NMR and the Kozeny-Carman equation. We determined the reasons for the low accuracy of the model through the theoretical analysis. We have developed the deep Boltzmann kernel extreme learning machine (DBKELM) to improve the deep-learning algorithm and to predict the reservoir permeability based on NMR logging with a deep Boltzmann machine (DBM). We use the permeability data of 200 rock specimens in a tight gas reservoir in a certain area and the corresponding spectra from NMR logging for modeling. We apply the model to the evaluation of permeability in this area. The results show that the accuracy of the deep-learning algorithm is higher than that of the existing NMR logging permeability model and the shallow layer machine-learning model. Furthermore, the accuracy of the DBKELM that we have developed is higher than that of the DBM, which indicates that DBKELM is more suitable for the prediction of reservoir permeability. Therefore, deep-learning theory can be effectively used in oil exploration and development, and it can improve the interpretation accuracy of reservoir parameters. These findings contribute to the interpretation of reservoir parameters.