P=NP 到底难在哪：排课表与电路布线才是真正的硬骨头
thesaraharminta · x · 2026-09-11
一则科普长帖的开头部分，作者认为很多人并不真正理解 P=NP 问题。
- 1960 年代以前，工程师默认算力每年变快，难题只要等更快的计算机就能解决。
- 但他们撞上了一类问题：无论计算机多强都会卡死，或需要上亿年才能算完。
- 这些并非高深的物理难题，而是日常问题，比如排一张老师不会同时在两处的高中课表、在电路板上画不重叠的最短走线。
- 作者指出关键特性：一旦找到解，验证解却可以非常快——这正是 P=NP 的核心张力。
注：原帖为线程开头，后续内容未包含在本帖中。
「研究」频道最新
- 《Steerable Visual Representations》登ICML长口头报告 — y_m_asano · 2026-09-11
- OpenCVL 卫星图像配准数据集亮相 ECCV 2026 — ducha_aiki · 2026-09-11
- Diverse VPR 视觉场所识别工作投稿 ECCV 2026 — ducha_aiki · 2026-09-11
- 哈工大提出 EASE:证据锚定空间注意力,让多模态 RLVR 答对也看对地方 — jiqizhixin · 2026-09-11
- 技术假说:ASI 会因数学激励而永久保护人类多样性 — No_Cause_2731 · 2026-09-11
- MutexaGPT:LLM翻译直觉,分子动力学筛选酶突变,命中率40% — bravo_abad · 2026-09-11