将数组元素映射到完美的哈希索引 NP Complete 吗？
Is mapping array elements to perfect hash indexes NP Complete?
假设我有一组整数，范围从 0 到 INT64MAX，但我知道整个集合，所以我可以生成一个完美的散列。
如果我想将这些散列用作数组索引，我需要对要存储它的数组的大小取模。
这带来了一个问题，我想为映射到整数的哈希找到一个非冲突集，这样需要最小的数组大小并且我仍然没有冲突。
这个NP完整吗？它 "feels" NP 完全。
没有
存在在线性时间内构建完美哈希（甚至最小完美哈希）的算法。例如，参见列出其中几个的 CMPH 文档。
线性时间意味着确定性多项式问题，因此问题出在P。 P包含在NP中，但问题肯定至少没有NP中最难的问题那么难，因此它不在NP-hard.
中
NP-complete 定义为 NP 和 NP-hard。因此，它不是NP完全的。
假设我有一组整数，范围从 0 到 INT64MAX，但我知道整个集合，所以我可以生成一个完美的散列。
如果我想将这些散列用作数组索引，我需要对要存储它的数组的大小取模。
这带来了一个问题，我想为映射到整数的哈希找到一个非冲突集，这样需要最小的数组大小并且我仍然没有冲突。
这个NP完整吗？它 "feels" NP 完全。
没有
存在在线性时间内构建完美哈希（甚至最小完美哈希）的算法。例如，参见列出其中几个的 CMPH 文档。
线性时间意味着确定性多项式问题，因此问题出在P。 P包含在NP中，但问题肯定至少没有NP中最难的问题那么难，因此它不在NP-hard.
NP-complete 定义为 NP 和 NP-hard。因此，它不是NP完全的。