计算复杂性理论是研究求解计算问题所需资源的学科。它为分析算法效率提供了框架——在算力与数据存储日益重要的时代，这一问题愈发关键。该学科的核心目标在于理解计算问题的固有难度以及高效计算的局限性。

时间、空间与大 O 表示法

从根本上说，计算复杂性理论关注的是算法求解一个问题所需的时间和空间。时间复杂度指算法完成所需的步骤数，而空间复杂度指其占用的内存量。这两项指标是评估算法效率的基础，通常用大 O 表示法来表达，即给出所需步骤数或空间量的上界。由于大 O 描述的是资源消耗相对于输入规模的增长方式，而非在特定硬件上的原始速度，它使算法能够在脱离具体机器的情况下进行比较。

P 与 NP：基本复杂度类

计算复杂性理论中最重要的两个复杂度类是 P（Polynomial Time，多项式时间的缩写）和 NP（Nondeterministic Polynomial Time，非确定性多项式时间的缩写）。P 包含可由确定性图灵机在多项式时间内求解的判定问题，即运行时间至多随输入规模呈多项式增长。相比之下，NP 包含这样一类判定问题：其候选解可由确定性图灵机在多项式时间内验证，但解本身未必能被快速求出。

P 是否等于 NP，是计算机科学中最深刻的未解问题之一。若 P=NP，则每一个已知存在高效验证方法的问题，也同样存在求解它的高效算法。若 P≠NP，则存在某些问题，即使其解可以被高效验证，也不存在高效算法。这一问题分量之重，体现在它被列为克雷数学研究所设立的七个千禧年大奖难题之一，每个问题的解答均可获得 100 万美元奖金。该问题的解答对密码学、优化问题以及科学与工程的许多领域意义重大，因为现代密码学在很大程度上建立在“某些问题在攻击者实际可行的时间范围内无法求解”这一假设之上。

归约与 NP 完全性

证明问题难度的关键概念是归约，即将一个问题转化为另一个问题。若问题 A 可归约到问题 B，且已知 B 是困难的，则 A 至少与 B 同样困难。NP 完全问题是 NP 中那些至少与 NP 中最难问题同样困难的问题。若任一 NP 完全问题被找到多项式时间解法，则 P=NP。NP 完全问题的著名例子包括旅行商问题、布尔可满足性问题（SAT）和背包问题。这类问题绝非纯粹的学术话题：它们频繁出现在路由、调度和资源分配中，在缺乏高效精确算法的情况下，从业者通常转向近似算法和启发式方法，以牺牲最优性保证来换取可接受的运行时间。

计算复杂性理论为理解算法效率的 intricacies 和计算的极限提供了丰富的框架。透过 P、NP 与归约的视角，研究者得以洞察高效求解复杂问题的根本挑战。随着计算在日常生活中扮演越来越重要的角色，计算复杂性理论的研究依然至关重要，它指引我们走向更高效的解决方案，并揭示计算的边界。在 P 与 NP 问题得到解答之前，“已知存在高效解法的问题”与“尚未找到高效解法的问题”之间的界线，将持续影响研究方向与工程实践。

来源：OPEC