Задача здійсненності булевих формул: відмінності між версіями

У 1971-му році в статті [[Кук, Стівен|Стівена Кука]] був уперше введений термін "[[NP- повна задача]]", і задача SAT була першою задачею, для якого доводилася ця властивість.

У доказі [[Теорема Кука|теореми Кука]] кожна задача з [[класКлас складності NP|класу NP]] в явному виді зводиться до SAT. Після появи результатів, Куком була доведена NP-повнота для безлічі інших задач. При цьому найчастіше для доказу NP-повноти деякої задачі наводиться [[поліноміальне зведення]] задачі SAT до цієї задачі, можливо в декілька кроків, тобто з використанням декількох проміжних задач.