计算复杂度与神经网络架构解析

# 计算复杂度与神经网络架构解析 ## 1. 时间复杂度类 解决某些问题的难度可以分为不同的时间复杂度类，常见的重要复杂度类如下： - **P**：能在多项式时间内解决的问题。 - **NP**：其解能在多项式时间内验证的问题。 - **NP - hard**：至少和NP中最难的问题一样难的问题。 - **NP - complete**：既是NP - hard又是NP的问题。 一般认为P ≠ NP，但这尚未得到证明，仍是数学中最重要的未解决问题之一。现代密码学依赖于没有已知的高效（即多项式时间）算法来解决NP - hard问题这一事实。 判断一个特定问题Q是否为NP - hard的常用方法是，找到一个从已知的NP - complete问题Q′到Q的实例的多项式变换。3SAT问题是已知的第一个NP - complete问题。 ## 2. 空间复杂度类 另一组复杂度类与空间有关，指的是执行一个算法直至完成所需的内存量。复杂度类PSPACE包含所有可以用多项式数量的空间解决的问题，而不考虑时间。时间复杂度和空间复杂度有根本区别，时间不能复用，但空间可以。已知P和NP是PSPACE的子集，虽然还不确定，但怀疑PSPACE包含不在NP中的问题。通过多项式时间变换，可以定义PSPACE - hard和PSPACE - complete类，就像定义NP - hard和NP - complete类一样。 ## 3. 布尔可满足性问题 布尔可满足性问题涉及确定一个布尔公式是否可满足。布尔公式由涉及n个布尔变量x1, ..., xn的合取（∧）、析取（∨）和否定（¬）组成。文字是变量xi或其否定¬xi。3SAT子句是最多三个文字的析取（例如，x3 ∨ ¬x5 ∨ x6）。3SAT公式是3SAT子句的合取。 例如： ```plaintext F(x1, x2, x3, x4) = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x2 ∨ ¬x3 ∨ x4) ``` 3SAT的挑战在于确定是否存在对变量的真值赋值，使得公式为真。对于上述公式，F(true, false, false, true) = true，因此该公式是可满足的。虽然对于某些3SAT问题，有时通过快速检查就能轻松找到满足赋值，但一般来说它们很难解决。一种确定是否可以进行满足赋值的方法是枚举所有变量的2n种可能的真值。虽然确定是否存在满足的真值赋值很困难，但验证一个真值赋值是否导致满足可以在线性时间内完成。 ## 4. 可判定性 不可判定问题不能总是在有限时间内解决。最著名的不可判定问题之一是停机问题，即输入任何用足够表达性的语言编写的程序，判断它是否会终止。已经证明，一般情况下没有算法可以进行这样的分析。虽然存在可以正确确定某些程序是否终止的算法，但没有算法可以确定任何任意程序是否会终止。 ## 5. 神经网络基础 神经网络是非线性函数的参数化表示，它表示的函数是可微的，允许使用基于梯度的优化算法（如随机梯度下降）来优化其参数，以更好地逼近所需的输入 - 输出关系。神经网络可以在与决策相关的各种上下文中发挥作用，例如表示概率模型、效用函数和决策策略。 ### 5.1 神经网络 神经网络是一个可微函数y = fθ(x)，它将输入x映射为输出y，并由参数θ进行参数化。现代神经网络可能有数百万个参数，可用于将高维图像或视频形式的输入转换为高维输出，如多维分类或语音。 网络的参数θ通常被调整以最小化一个标量损失函数ℓ(fθ(x), y)，该函数与网络输出与期望输出之间的距离有关。损失函数和神经网络都是可微的，这使我们能够使用损失函数相对于参数化的梯度∇θℓ来迭代改进参数化。这个过程通常被称为神经网络训练或参数调整。 例如，考虑一个非常简单的神经网络fθ(x) = θ1 + θ2x，我们希望它根据房屋的平方英尺数x预测其价格ypred。通过损失函数ℓ(ypred, ytrue) = (ypred - ytrue)²来最小化预测房价与真实房价之间的平方偏差。给定一