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