NP-полное определение выполнимости формулы в конъюнктивной нормальной форме, в которой каждое предложение ограничено не более чем тремя литералами; эта проблема называется «3SAT», «3CNFSAT» или «3-выполнимость». Определение выполнимости формулы, в которой каждое предложение ограничено не более чем двумя литералами, является NL-полным; эта проблема называется «2SAT».
В каждом предложении есть несколько литералов.