как судоку np-complete?

как судоку является np-полной проблемой? согласно вики, чтобы быть классифицированной как np-полная проблема, она должна удовлетворять 2 условиям

  1. проблема должна быть в np
  2. любая другая проблема в np должна быть сведена к данной задаче за полиномиальное время

как выполняется второе условие? можете привести пример? например, я не вижу никакой связи между задачей судоку и задачей коммивояжера или задачей рюкзака.

(прошу прощения за плохое форматирование, так как я набираю этот вопрос на своем мобильном устройстве)


sudoku np-complete
person Ashish K    schedule 02.11.2016    source источник
comment
Это, вероятно, был бы лучший вопрос для компьютерных наук, и, вероятно, он будет закрыт как не относящийся к теме, но в основном существует сокращение полиномиального времени из задачи завершения латинского квадрата (вы можете видеть это сокращение здесь), который имеет полиномиальное сокращение времени по сравнению с SAT. Вы можете свести любую задачу NP к SAT, и, поскольку вы можете решить SAT, решая заполнение латинского квадрата, и вы можете решить заполнение латинского квадрата, решая судоку, вы можете решить любую задачу NP, решая судоку.   -  person Paul    schedule 03.11.2016

Ответы (1)


arrow_upward
2
arrow_downward

NP-полнота судоку примечания частично :

Этот результат был впервые показан в этой магистерской диссертации путем редукции из NP-полной задачи ЗАВЕРШЕНИЕ ЛАТИНСКОГО КВАДРАТИКА. Страница Судоку в Википедии.

Вот как это работает (упрощенно, без привязки к ASP-полноте, которую я не рассматриваю в этом курсе).

Предположим, у нас есть n×n экземпляр LATIN SQUARE COMPLETION. Мы создаем экземпляр n2×n2 SUDOKU, который кодирует экземпляр LATIN SQUARE COMPLETION. Более того, кодирование очень прямое.

http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf является ссылкой на диссертацию в формате PDF.

person JB King    schedule 02.11.2016