47、计算复杂度相关问题探讨

计算复杂度相关问题探讨

1. 复杂度的基本概念

首先来看布尔函数 PARITY(x1,x2,…,xn)，它用于计算输入中 1 的数量的奇偶性。如果 x1 到 xn 中 1 的数量为偶数，输出为 0；否则输出为 1。若要将其表示为变量和否定变量的合取的析取形式，即：
PARITY(x1,x2,…,xn) = ∨i ∧j zij
其中每个 zij 是变量或否定变量（对于某个 k = 1 到 n，为 xk 或 ¬xk）。
- 如果某个合取式 ∧j zij 包含少于 n 个变量，那么等式右边会接受两种奇偶性的输入，这是不可能的。
- 如果一个合取式包含所有变量（假设每个变量只出现一次），那么它恰好接受一个输入。因此，合取式的数量必须是 2n - 1，即奇数输入的数量，这是一个很容易得到的下界。

对于深度为 3 的电路，即把 PARITY 表示为：
PARITY(x1,x2,…,xn) = ∨i ∧j ∨k zijk
其中每个 zijk 是变量或否定变量，仍然可以证明一个指数下界 2√n，但证明并不简单。更一般地，对于任何固定深度都可以证明指数下界，证明基于随机限制方法。

这里值得注意的是，用于证明下界的函数 PARITY 非常简单。通常人们会认为，对于复杂的函数证明下界会更容易，但实际上这个简单函数利用了一个特性：只要翻转任何一个输入位，PARITY 的值就会改变，这个函数及其否定是具有此特性的唯一函数。这是最早的非平凡下界之一，近期的结果使用了更复杂一些的性质，但仍然相对简单，这表明该领域还不够成熟。

2. 存在性证明与构造性证明

在数学中，当证明具有某种性质的数学实体（如数字、数学