alt text

Помогите, пожалуйста, тут также необходимо показать явную сводимость.

задан 2 Май 23:20

Смысл обозначения <= с индексами m и p "широкому читателю" может не быть известен. Такие вещи надо пояснять, или давать ссылки.

(3 Май 1:03) falcao

@Falcao, <= это знак сводимости, m-сводимость за p- полиномиальное время. https://neerc.ifmo.ru/wiki/index.php?title=M-сводимость. Спасибо

(3 Май 12:13) Intersection

@Falcao, плюс вот еще ссылка https://docplayer.ru/61152849-Zadanie-4-slozhnost-vychisleniy-klassy-p-np-i-co-np.html страница 7 про сводимость.

(4 Май 8:57) Intersection
10|600 символов нужно символов осталось
1

Для любых 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 за полиномиальное время, откуда вытекает требуемый факт сводимости.

ссылка

отвечен 4 Май 13:49

@falcao, спасибо огромное!!!

(4 Май 14:53) Intersection
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×54

задан
2 Май 23:20

показан
136 раз

обновлен
4 Май 14:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru