sudoku - 数独 np 完整吗？

Question

我确实经历过这个。

我不明白这一点。

数独在推广到 × n 网格时是 NP 完全的，但是标准的 9 × 9 数独不是 NP 完全的。

标签： sudokunp-complete

Answer 1

正确的; 任何 9x9 数独都可以在 O(1) 时间内解决（1x1 数独，或 4x4 数独，甚至 1000x1000 数独），因为输入大小是固定的。NP 完全性是一个适用于具有可变输入大小的决策问题的概念，因此您可以在输入大小渐近增长时分析算法的运行时间。

区别在于算法是否可以假设输入的大小，或者必须等到它接收到输入才能看到它有多大。

输入不必以二进制编码；它只需要使用一些有限大小的字母表。对于固定大小的数独，您可以为每个可能的谜题选择一个具有一个唯一符号的字母表。（实际上，您可以用二进制编码理论字母表，每个字母符号都有一个固定大小的二进制字符串。这就是 ASCII 的工作原理。输入大小仍然是恒定的；它只是一个大于 1 的常数。）然后，该算法使用一个硬编码表，将输入字母表中的每个符号与其解决方案配对。解决这个难题的恒定时间算法只是一个查表。

现在考虑谜题没有固定大小的问题。有无数个可能的谜题，因此算法必须指定一些编码方案，该方案可以使用有限大小的字母表来描述无数个谜题。这有两个直接后果。

1. 您无法将所有可能输入的解决方案存储在有限的空间中，因此您的算法需要在看到输入后进行实际工作来解决难题。

2. 并非所有输入都具有相同的大小，因为来自有限字母表的固定符号串只能编码有限数量的谜题。一旦输入具有不同的大小，您可以根据输入大小考虑算法必须做的工作量。（现在只读取输入是一个 O(n) 操作；解决问题所需的工作可能而且通常更大。）