关于巨型哈希表实现多项式时间数独求解的合理性问询

首先直接给结论：单看查询阶段，这个方法确实是常数时间（属于多项式时间范畴），但这个方案从现实可行性和算法复杂度的定义来说，完全不能算作有效的多项式时间数独求解器，核心问题出在预处理阶段的致命缺陷：

1. 空间需求完全超出人类可实现的范围 #

标准数独的完整解大约有 6.67×10^21 个，而有效未完成数独的数量更是远远超过这个数字——每个完整解可以衍生出无数种不同的未完成状态（比如挖掉1个格子、2个格子……直到只剩少数几个格子）。哪怕每个数独状态只占用1字节的存储，整个哈希表需要的空间也是宇宙级别的，没有任何存储介质能容纳这么多数据，甚至把整个宇宙的物质都转化为存储设备都不够。

2. 预处理时间是天文数字 #

要构建这个哈希表，你需要先枚举所有有效的未完成数独，再计算它们的对应解。但数独是NP完全问题，枚举所有可能的状态需要指数级的时间——哪怕用目前最快的超级计算机，从宇宙诞生到现在的时间都远远不够完成这个预处理过程。

3. 算法复杂度的定义误区 #

通常我们说的“多项式时间算法”，指的是从接收输入到输出结果的整个流程的时间复杂度是多项式的。这个方案只把查询阶段算进去，忽略了必须先完成的预处理步骤，而预处理的时间是指数级的，所以整体不能被认定为多项式时间算法。

另外，这种“预存所有可能输入”的思路，本质上是查表法，对于输入空间极大的问题（比如数独）来说，完全没有现实意义——你根本不可能提前把所有可能的输入都准备好。

内容的提问来源于stack exchange，提问作者svaerth