5.1 经典复杂性类回顾（P, NP, BPP）

文档摘要

5.1 经典复杂性类回顾（P, NP, BPP） 5.1 经典复杂性类回顾（P, NP, BPP）在量子计算的宏大叙事中，我们常将目光投向叠加、纠缠与量子门操作等令人炫目的物理现象。然而，若要真正理解量子算法为何能“超越经典”，我们必须先回望那片奠定整个计算科学根基的土壤——经典复杂性理论。它如同一座沉默而坚实的地基，支撑起所有关于“可计算性”与“计算效率”的追问。当我们谈论“量子加速”时，其本质并非凭空诞生，而是建立在对经典复杂性类深刻认知之上的对比与突破。因此，在迈向量子算法的深水区之前，我们必须重新梳理那些塑造了计算思维的基本框架：P、NP 与 BPP。一、从可解到可高效求解：复杂性类的诞生想象你面对一个谜题：给定一组数字，能否从中选出若干个，使得它们的和恰好等于某个目标值？