2-выполнимость применяется в практических задачах, которые сводятся к задаче о выполнимости булевых формул (SAT). 35 По данной булевой формуле определяют, принимает ли она значение 1 хотя бы на одном наборе аргументов. 3

Некоторые примеры задач, которые сводятся к выполнимости КНФ:

• Задача о 3-раскраске вершин графа. 1 Задан неориентированный граф, нужно определить, можно ли раскрасить его вершины в 3 цвета так, чтобы вершины одного цвета не были соединены ребром. 1
• Задача о расстановке ферзей на шахматной доске. 1 Нужно найти решение этой задачи, в которой ферзи расставляются на шахматной доске. 1