alizar Sep 3 2017 at 15:19

Задачу о N ферзях признали NP-полной задачей

3 min

39K

+20

Comments 46

qw1 Sep 3 2017 at 19:43

Интересно, они свели 1-in-3-SAT (т.е. NP-полную задачу) к задаче расстановки ферзей.
Научимся расставлять ферзей — научимся решать SAT

ripatti Sep 3 2017 at 22:03

Класс #P принадлежит к классу NP...

Тут какой-то бред написан. Мало того, что любая задача из #P не проще аналогичной из NP, они еще и в разных «весовых категориях» — у задачи из #P на выходе число (counting problem), а у задачи из NP — «да» или «нет» (decision problem), и для «да» есть сертификат, проверяемый за полином. И вот мы для задачи из #P получили число — и как мы проверим за полином, что это число верное, раз эта задача еще и в NP лежит?

alizar Sep 3 2017 at 23:13

Я исправил формулировку, действительно, было не совсем корректно. Спасибо, что обратили внимание!

CDCrom Sep 3 2017 at 22:17

В головоломке говорится о том, что нужно на доске 8 на 8 расположить 8 ферзей, а то у меня для указанного варианта получилось 7 ферзей покрывающих все поле.

CDCrom Sep 3 2017 at 22:18

Простите, я не правильно прочел статью… перечитал, понял, что нельзя писать на ночь глядя… а отменить отправку уже не смог:(

LoadRunner Sep 3 2017 at 23:26

О, так вот как называется задача о 9 мухах. И судоку, в принципе, тоже из этого же класса задач.

А в представленных в статье 2 решениях две группы по 3 ферзя просто переставлены. Что приводит к мысли, что для нахождения всех решений надо найти одно верное, а все остальные получаются из всех возможных перестановок.

qw1 Sep 4 2017 at 00:42

Для доски 4x4 есть всего 2 решения (причём одно получается из другого зеркальным отражением или поворотом). Что тут можно попереставлять?

-X--

---X

X---

--X-

LoadRunner Sep 4 2017 at 08:42

Зеркальное отражение — это просто название одной из перестановок.
В случае N=4, других просто нет. Ну и 4 — минимальное число для данной задачи.
Не спорю, зеркальные отражения и повороты не порождают новых вариантов, а являются эквивалентом уже существующих. Но эти эквиваленты легко получаются перестановками.

darkdaskin Sep 4 2017 at 09:35

4 — минимальное число для данной задачи

Формально есть ещё одно решение для доски 1×1.

LoadRunner Sep 4 2017 at 10:14

Только для 2 и 3 решений нет. Так что можно 1 не принимать в расчёт :)

qw1 Sep 4 2017 at 12:25

Тогда, в принципе, любую расстановку можно назвать перестановкой другой расстановки.

Вы хотели подчеркнуть какое-то более интересное свойство? Не просто перестановку, а перестановку группы?

varagian Sep 4 2017 at 01:03

Заголовок не верен, да ещё и пост не проясняет суть статьи *злой и расстроенный смайл одновременно*.

Задача в варианте:

найти решение в виде N ферзей на доске N*N — в P (вообще там чуть ли не линейное время);
найти число решений для доски N*N — не имеет решения в закрытой форме (вне #P);
дополнение доски N*N до N ферзей, уже имея M (<N) — NP-complete и #P-complete (в этом результат статьи!).

(Если что, это всё написано в самой статье в разделе Introduction.)

Sayonji Sep 4 2017 at 13:11

NP-полным будет только вопрос о том, сколько решений? Или есть ли хотя бы одно решение уже тоже NP-полная задача?

varagian Sep 4 2017 at 13:17

Сколько решений вообще выше, чем #P и NP — то есть у нас вообще нет никакой аналитической формулы для решения.

Если доска пустая, то одно решение находится за линейное время (кажется линейное, но точно в P, то есть полином — корочь, точно не NP-полна задача).

Если доска не пустая и на ней уже стоит M ферзей и всего нужно N, т.е. нужно ещё N — M доставить до N, то задача NP-полна, как следует из только что опубликованной статьи.

erwins22 Sep 4 2017 at 15:08

Тогда за что 1млн баксов????

qw1 Sep 4 2017 at 15:57

За решение задачи дополнения.
Т.е. на доске NxN стоит M ферзей (M < N).
Нужно доставить N-M, чтобы получилось N, либо определить, что в данной конфигурации это невозможно. И сделать это за P-время.

erwins22 Sep 4 2017 at 16:20

Надо найти число таких комбинаций, все такие комбинации или просто факт, если или нет?
У этих задач разная оценка сложности.

qw1 Sep 4 2017 at 17:05

Надо найти одну комбинацию или доказать, что такой нет.

erwins22 Sep 4 2017 at 17:12

Спасибо.
Доказать что есть без предъявления конкретной пройдет?

varagian Sep 4 2017 at 17:59

Не, если ответ «да», то нужно вернуть сертификат проверяемый за полиномиальное время.

В данном случае, N ферзей (ну или N-M сути в общем-то не играет).

qw1 Sep 4 2017 at 23:24

Доказать что есть без предъявления конкретной пройдет?

А сможете формализовать?

Решение SAT-задачи — вектор значений переменных.
Решение задачи расстановки — координаты ферзей.

Сможете придумать «доказательство» в виде числового вектора, правильность которого (т.е. то, что он есть доказательство, а не рандомный набор) можно проверить за P-время?

Если сможете, то пройдёт. Т.е. нужно научиться генерировать такие вектора за P-время и уметь их проверять за P-время.

erwins22 Sep 4 2017 at 23:41

аналогия — проверка простоты числа без указания конкретного делителя.

qw1 Sep 5 2017 at 15:09

Непонятная аналогия. Я знаю, есть правила деления на 3, 5 и т.д.

Т.е. в частных случаях мы можем быстро сказать «Нет, не не простое». Но не можем быстро сказать «да» или «нет» во всех случаях.

erwins22 Sep 5 2017 at 15:18

Есть алгоритм N^6 где N — количество битов числа.

qw1 Sep 5 2017 at 20:30

Как называется алгоритм?

erwins22 Sep 5 2017 at 20:32

Тест Агравала — Каяла — Саксены

Sayonji Sep 5 2017 at 12:38

Пройдет, «сертификат» это всё шелуха. Если ваша программа будет правильно отвечать ДА/НЕТ на данную задачу за полиномиальное время, то, используя её как функцию, можно будет на все NP задачи правильно отвечать ДА/НЕТ, это определение NP-сложной задачи.

Альтернативный ответ на ваш вопрос: если у вас есть алгоритм, правильно отвечающий ДА/НЕТ, то можно, получив ответ ДА, доставлять одного ферзя всеми способами и искать такого, что ответ вашего алгоритма будет снова ДА. Как только найдем, пытаться ставить следующего. И так далее, мы за N^3 попыток поставим всех ферзей, т. е. на полином запусков вашего алгоритма найдем «сертификат».

qw1 Sep 5 2017 at 15:06

И даже за N^2 попыток, если не пытаться ставить ферзя на уже занятую линию.

cujos Sep 4 2017 at 07:15

За доказательство, что существует более эффективный способ решения задачи, чем простой перебор всех вариантов, дадут миллион долларов.

Как-то не однозначно звучит. Кому в голову придет перебирать «все» варианты? Потому как добавление каждого ферзя убирает 3.х*n заведомо неверных вариантов расстановки нового ферзя. Запилить рекурсию и перебирать из оставшихся не так сложно. Или они хотят алгоритм расстановки каждого следующего ферзя в заведомо правильное место?

Fil Sep 4 2017 at 10:42

Нужно найти алгоритм проще, чем O(n!). В идеале O(n^c) или хотя бы O(cⁿ)

menfromearth Sep 4 2017 at 11:37

Да тут вся статья признана запутать читателя, похоже. Одна фраза «не только #P-полной задачей, но также NP-полной» чего стоит. Естественно, формально, требуется найти полиномиальный по времени алгоритм. Лучше прочитайте исходную статью — там и само доказательство несложное (особенно, ели сравнить с аналогичными результатами в выч геоме).