检索库构成(离线快照)
· Wikipedia《List of NP-complete problems》——社区持续维护的动态列表,条目带 Garey & Johnson (1979) 编号
· Wikipedia Category:NP-complete problems 分类成员
· Crescenzi & Kann《A Compendium of NP Optimization Problems》KTH 索引(2000 年后停更,收录 NP 优化问题的可近似性结果)
在线原始站点
·
Wikipedia: List of NP-complete problems(事实上的"持续更新"清单,靠社区贡献)
·
Wikipedia 分类页
·
KTH Compendium of NP Optimization Problems(自带搜索,但 2000 年停更)
·
Complexity Zoo(复杂度类百科,仍在更新)
口径说明
· 已知的 NP 完全问题数以千计(Garey & Johnson 1979 附录即收录 300+,此后新增更多),本库收录的是最常被引用的一批子集,不是全集。
· 「做不到」指的是:
不存在已知的多项式时间精确算法,不等于任何实例都算不出来。小规模、受限参数、近似解、启发式都仍可解——想拒绝得更严谨,就把这条一起附上。