сложность-алгоритма - Задачи на сложность

Для любых i,j,k от 1 до n^2 введём булеву переменную p(i,j,k), которая равна 1 iff значение клетки квадрата с координатами i,j равно k. Это даёт n^6 высказывательных переменных. Для тех клеток, где уже находится число k, полагаем p(i,j,k)=1 и p(i,j,m)=0 для m не равных k.

Для каждой из n^2 строк запишем условие, согласно которому никакие два значения p(i,j,k) не равны одновременно 1, где i фиксировано, k принимает каждое из значений от 1 до n^2, и при этом перебираются все пары вида j1 < j2. Также потребуем, чтобы для любого k, в i-й строке нашлась клетка, для которой p(i,j,k)=1. Такие условия задаются формулой полиномиального размера.

То же самое делаем со столбцами, а также с "малыми" квадратами, где суть ограничений та же, но расписывать это всё покоординатно не будем. В итоге получится формула полиномиального от n размера, если рассмотреть конъюнкцию рассмотренных выше условий. Стандартными методами это всё записывается в виде КНФ.

Если мы умеем решать SAT за полиномиальное время, то есть проверять формулу на выполнимость, то из этого следует решение проблемы SUDOKU за полиномиальное время, откуда вытекает требуемый факт сводимости.