Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 46
Интересно, они свели 1-in-3-SAT (т.е. NP-полную задачу) к задаче расстановки ферзей.
Научимся расставлять ферзей — научимся решать SAT
Научимся расставлять ферзей — научимся решать SAT
Класс #P принадлежит к классу NP...
Тут какой-то бред написан. Мало того, что любая задача из #P не проще аналогичной из NP, они еще и в разных «весовых категориях» — у задачи из #P на выходе число (counting problem), а у задачи из NP — «да» или «нет» (decision problem), и для «да» есть сертификат, проверяемый за полином. И вот мы для задачи из #P получили число — и как мы проверим за полином, что это число верное, раз эта задача еще и в NP лежит?
В головоломке говорится о том, что нужно на доске 8 на 8 расположить 8 ферзей, а то у меня для указанного варианта получилось 7 ферзей покрывающих все поле.
О, так вот как называется задача о 9 мухах. И судоку, в принципе, тоже из этого же класса задач.
А в представленных в статье 2 решениях две группы по 3 ферзя просто переставлены. Что приводит к мысли, что для нахождения всех решений надо найти одно верное, а все остальные получаются из всех возможных перестановок.
А в представленных в статье 2 решениях две группы по 3 ферзя просто переставлены. Что приводит к мысли, что для нахождения всех решений надо найти одно верное, а все остальные получаются из всех возможных перестановок.
Для доски 4x4 есть всего 2 решения (причём одно получается из другого зеркальным отражением или поворотом). Что тут можно попереставлять?
-X--
---X
X---
--X-
Зеркальное отражение — это просто название одной из перестановок.
В случае N=4, других просто нет. Ну и 4 — минимальное число для данной задачи.
Не спорю, зеркальные отражения и повороты не порождают новых вариантов, а являются эквивалентом уже существующих. Но эти эквиваленты легко получаются перестановками.
В случае N=4, других просто нет. Ну и 4 — минимальное число для данной задачи.
Не спорю, зеркальные отражения и повороты не порождают новых вариантов, а являются эквивалентом уже существующих. Но эти эквиваленты легко получаются перестановками.
Заголовок не верен, да ещё и пост не проясняет суть статьи *злой и расстроенный смайл одновременно*.
Задача в варианте:
- найти решение в виде N ферзей на доске N*N — в P (вообще там чуть ли не линейное время);
- найти число решений для доски N*N — не имеет решения в закрытой форме (вне #P);
- дополнение доски N*N до N ферзей, уже имея M (<N) — NP-complete и #P-complete (в этом результат статьи!).
(Если что, это всё написано в самой статье в разделе Introduction.)
NP-полным будет только вопрос о том, сколько решений? Или есть ли хотя бы одно решение уже тоже NP-полная задача?
Сколько решений вообще выше, чем #P и NP — то есть у нас вообще нет никакой аналитической формулы для решения.
Если доска пустая, то одно решение находится за линейное время (кажется линейное, но точно в P, то есть полином — корочь, точно не NP-полна задача).
Если доска не пустая и на ней уже стоит M ферзей и всего нужно N, т.е. нужно ещё N — M доставить до N, то задача NP-полна, как следует из только что опубликованной статьи.
Если доска пустая, то одно решение находится за линейное время (кажется линейное, но точно в P, то есть полином — корочь, точно не NP-полна задача).
Если доска не пустая и на ней уже стоит M ферзей и всего нужно N, т.е. нужно ещё N — M доставить до N, то задача NP-полна, как следует из только что опубликованной статьи.
Тогда за что 1млн баксов????
За решение задачи дополнения.
Т.е. на доске NxN стоит M ферзей (M < N).
Нужно доставить N-M, чтобы получилось N, либо определить, что в данной конфигурации это невозможно. И сделать это за P-время.
Т.е. на доске NxN стоит M ферзей (M < N).
Нужно доставить N-M, чтобы получилось N, либо определить, что в данной конфигурации это невозможно. И сделать это за P-время.
Надо найти число таких комбинаций, все такие комбинации или просто факт, если или нет?
У этих задач разная оценка сложности.
У этих задач разная оценка сложности.
Надо найти одну комбинацию или доказать, что такой нет.
Спасибо.
Доказать что есть без предъявления конкретной пройдет?
Доказать что есть без предъявления конкретной пройдет?
Не, если ответ «да», то нужно вернуть сертификат проверяемый за полиномиальное время.
В данном случае, N ферзей (ну или N-M сути в общем-то не играет).
В данном случае, N ферзей (ну или N-M сути в общем-то не играет).
Доказать что есть без предъявления конкретной пройдет?А сможете формализовать?
Решение SAT-задачи — вектор значений переменных.
Решение задачи расстановки — координаты ферзей.
Сможете придумать «доказательство» в виде числового вектора, правильность которого (т.е. то, что он есть доказательство, а не рандомный набор) можно проверить за P-время?
Если сможете, то пройдёт. Т.е. нужно научиться генерировать такие вектора за P-время и уметь их проверять за P-время.
аналогия — проверка простоты числа без указания конкретного делителя.
Пройдет, «сертификат» это всё шелуха. Если ваша программа будет правильно отвечать ДА/НЕТ на данную задачу за полиномиальное время, то, используя её как функцию, можно будет на все NP задачи правильно отвечать ДА/НЕТ, это определение NP-сложной задачи.
Альтернативный ответ на ваш вопрос: если у вас есть алгоритм, правильно отвечающий ДА/НЕТ, то можно, получив ответ ДА, доставлять одного ферзя всеми способами и искать такого, что ответ вашего алгоритма будет снова ДА. Как только найдем, пытаться ставить следующего. И так далее, мы за N^3 попыток поставим всех ферзей, т. е. на полином запусков вашего алгоритма найдем «сертификат».
Альтернативный ответ на ваш вопрос: если у вас есть алгоритм, правильно отвечающий ДА/НЕТ, то можно, получив ответ ДА, доставлять одного ферзя всеми способами и искать такого, что ответ вашего алгоритма будет снова ДА. Как только найдем, пытаться ставить следующего. И так далее, мы за N^3 попыток поставим всех ферзей, т. е. на полином запусков вашего алгоритма найдем «сертификат».
За доказательство, что существует более эффективный способ решения задачи, чем простой перебор всех вариантов, дадут миллион долларов.
Как-то не однозначно звучит. Кому в голову придет перебирать «все» варианты? Потому как добавление каждого ферзя убирает 3.х*n заведомо неверных вариантов расстановки нового ферзя. Запилить рекурсию и перебирать из оставшихся не так сложно. Или они хотят алгоритм расстановки каждого следующего ферзя в заведомо правильное место?
Нужно найти алгоритм проще, чем O(n!). В идеале O(nc) или хотя бы O(cn)
Да тут вся статья признана запутать читателя, похоже. Одна фраза «не только #P-полной задачей, но также NP-полной» чего стоит. Естественно, формально, требуется найти полиномиальный по времени алгоритм. Лучше прочитайте исходную статью — там и само доказательство несложное (особенно, ели сравнить с аналогичными результатами в выч геоме).
Да, он значит, что нет пересечений по строке, столбцу и диагонали. Это минимальное расстояние между двумя клетками, которые удовлетворяют данному правилу.
А для четного N?
На самом же деле, задача была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Гаусс же нашел 72 решения, которые и сообщил в письме к другу астроному Шумахеру в сентябре 1850 года. Полный набор решений состоит из 92 позиций. Существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать. Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски.
А интересно, есть ли уже на этой задаче криптовалюта? :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задачу о N ферзях признали NP-полной задачей