Für bestimmte echte Teilmengen der Formeln der aussagenlogischen Sprache ist das SAT-Problem dennoch schneller, d. h. in polynomial beschränkter Rechenzeit lösbar.
fyːɾ bəʃtˈɪmtə ˈɛçtə tˈaɪlmɛŋən dɛɾ fˈɔɾməln dɛɾ ˈaʊszˌɑːɡənlˌoːɡɪʃən ʃpɾˈɑːxə ɪst das ˌɛsˌɑːtˈeːpɾoːblˈeːm dˈɛnɔx ʃnˈɛlɜ, dˈeː. hˈɑː. ɪn pˌoːlyːnˌoːmiːˈɑːl bəʃrˈɛŋktɜ rˈɛçəntsˌaɪt lˈøːzbɑːɾ.