Является ли проблема N Queens NP-трудной?

Проблема N-королевы заключается в следующем:

Вход: N

Вывод: размещение N «ферзей» на шахматной доске NXN таким образом, чтобы никакие две королевы не лежали в одной строке, столбце или диагонали.

Сделав поиск в Google по этому вопросу, я обнаружил, что многие слайды многих профессоров утверждают, что это проблема NP-Hard (например, web.mst.edu/~ercal/387/slides/NP-Hard.ppt).

Однако я не смог найти доказательства (или получить одно). Причина, по которой я задаю этот вопрос, заключается в том, что я думаю, что у меня есть алгоритм, который решает определенные случаи проблемы, то есть с N, не кратным 2 или 3 (N - это число ферзей). Связанная проблема - Можем ли мы считать размер входного файла равным N (где N - количество королев)? Или мы принимаем входной размер равным log (N), поскольку число 'N' может быть представлено в log (N) битах?

cc.complexity-theory np-hardness csp Аншул Сингл
источник

(1) Почему вы используете N и n? Это одна и та же переменная или разные переменные? (2) Для каждого целого числа n, кроме 2 и 3, существует способ поместить n ферзей на доску n × n, удовлетворяющих условию n-ферзя (см. Википедию ), поэтому я не знаю, о какой проблеме вы говорите, когда Вы говорите: «Это сложная проблема для NP».

Цуёси Ито

Я помню, что результат твердости возникает, когда доска не обязательно квадратная, то есть форма платы задается как часть ввода.

Сашо Николов

Не может быть доказательства NP-полноты для шахматной доски, потому что эта задача имеет одинарный вход ... то есть, есть только один вход для размера , в то время как свидетель нуждается в описании размера полинома. Теорема Махани гласит, что показ такой задачи как NP-полной подразумевает, что P = NP. Вам нужны забавные формы доски, чтобы задача была NP-полной.

n \times n

$n \times n$

n

$n$

Питер Шор

Возможно, подсчет решений - немного более интересная проблема (за исключением класса #P, как доказано в «О сложности подсчета полных отображений»).

Марцио де Биаси

Смотрите также: dl.acm.org/citation.cfm?id=122322

Джефф

Ответы:

Как указано, ответ на этот вопрос НЕТ.

Ссылки: Алгоритм полиномиального времени http://dl.acm.org/citation.cfm?id=101343 [любезно предоставлено: vzn]

Еще один гораздо более простой метод: http://dl.acm.org/citation.cfm?id=122322 [любезно предоставлено Джеффом]

Аншул Сингл
источник

Вы можете принять этот ответ, чтобы он не появлялся снова без ответа.

Суреш Венкат

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

Цуёси Ито

Вторая ссылка также не является доказательством. То, что найдено единственное выполнимое решение для n-ферзей с n = 500000, не означает, что оно есть в P. (Это только повышает вероятность этого)

Джеффри Де Смет,

На самом деле, это только что было доказано.

https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/ ]

Kasper
источник

Нет, это не так. Прочитайте статью, или даже ее аннотацию: она имеет дело с завершением королев , вариантом проблемы.

N

$N$

Клемент С.

@ClementC. На самом деле, поскольку исходный вопрос недостаточно точен, я думаю, что у Каспера есть смысл, даже если его способ сформулировать это может быть неполным. Принимая во внимание n, если существует место, очевидно, что решение находится в P, поскольку задача всегда имеет решения для n> 3. Таким образом, проблема завершения n-ферзей (решение о том, можно ли расширить данное частичное решение) кажется естественной проблемой решения, которую нужно рассмотреть, чтобы понять сложность проблемы.

@holf Это действительно верное замечание, которое вы высказываете, но в этом ответе даже не упоминается (и что читатель совершенно не сможет его прочитать). Иметь неверный ответ на неоднозначный вопрос не совсем оптимально.

Климент С.