模拟求解器在NP难优化问题上超越数字计算机
- 研究人员构建新系统求解典型离散优化问题MaxSAT。
- 该模拟求解器优于数字计算机，可扩展至其他优化问题。
当今数字计算机执行大多数任务良好。适合特定计算、文字处理、网页浏览、图形艺术。但依赖二进制代码（0和1），不适合解决所有问题。
数字计算几乎达最大潜力，因此一些数学家开始重振模拟计算兴趣。可帮助推进超越数字框架的计算。
诺特丹大学和罗马尼亚巴贝什-博亚伊大学研究人员近期开发新模拟求解器，可评估NP难问题最优解。
NP难问题指无算法能多项式时间求解。求解时间随问题规模指数增长。通常与医学成像、生物信息学、蛋白质折叠、调度相关。
研究人员在广泛NP难问题测试模拟求解器，发现新方法有潜力在更短时间内得出更好解。
为何模拟计算？
模拟计算机20世纪中叶极流行。每大型机构和关注动力学问题公司都有巨型模拟计算中心。用于发射火箭入太空、引导战舰武器、模拟飞机动力学。
区别于数字计算机，模拟计算机用非离散数据：电压、重量、速度、温度、压力。因使用连续值，免疫量化噪声。
模拟计算机可设计解决多种问题。可直接执行数学运算。例如3减8，模拟计算机减去对应电压，立即给出正确输出。
可用于实时操作和并行计算。模拟问题时能提供问题和错误洞见。因不需量化，完美适用于信号调制/解调和高速电机控制。
参考：Nature Communications | doi:10.1038/s41467-018-07327-2 | 诺特丹大学
但数字计算机1980年代接管市场。它们足够灵活、快速、准确执行通用任务。高效算法出现后性能更强。
复古模拟AMF665D计算机 | 图片来源：Francis Massen / YouTube
但包括现代在内的数字计算机无法解决大变量NP难问题。大多数优化问题难点在于无法判断解是否最优。确保不存在更好解与问题本身同等困难。
高性能模拟求解器
新连续时间动力学系统可求解典型离散优化问题MaxSAT。方法依赖确定性常微分方程组和启发式技术，预测模拟时间t时最优解已评估的可能性。
模拟电路中冯·诺依曼瓶颈被消除：电路本身充当处理器和存储器。数字计算机实现该方法需用常微分方程积分器算法离散化连续时间方程并逐步求解同时处理误差。
数字形式下求解器不高效，因动力学演化数千耦合常微分方程，是耗时积分过程。
延伸阅读：关于量子计算机的最有趣事实
因方法使用通用特性，可扩展至其他优化问题。研究人员计划基于新方法设计制造设备。
工业技术