algorithm - 什么是电路？

Question

《算法》一书通过“电路”演示了快速傅立叶变换，使用“电线”来传输数据。什么是电路？它只是本书作者为了更好地演示算法而提出的概念，还是公认的计算机科学概念？

Answer 1

您的问题的答案是，是的，“电路”是理论计算机科学中公认的概念，借鉴了电子学的相关概念。布尔电路基本上就是它听起来的样子：一种用于计算二进制字符串的模型，由用电线串在一起的布尔逻辑门组成。您可以在 Wikipedia上找到正式的定义。

如您所见，它们派上用场的地方是确定特定问题的复杂性。FFT 的例子很容易理解，但最著名的例子可能是库克对 NP 完全性的定义，它证明了确定给定布尔电路是否可满足是 NP 完全的。

Barrington 和 Maciel 有一系列计算复杂性讲义，在第一讲中介绍了电路，并在整个过程中继续使用这个概念。

Answer 2

有些问题很容易，有些问题很难。为了说明什么使问题变得容易，什么使问题变得更复杂，我们通常使用计算机模型并对这些模型施加约束。

图灵机是一种用于定义问题类别的常用模型。例如，复杂度等级P包含这样的问题，即存在一个图灵机，它可以在 O(n^p) 时间内解决某个幂 p（多项式时间）的问题。我们可以在图灵机上获得具有其他时间或空间限制的其他复杂性类。

非确定性图灵机是计算机的另一种模型。 交替图灵机是另一种。存在许多计算机模型，每个模型都可用于定义不同类型的问题。 电路是这些计算机模型之一。

图灵机可用于对单线程计算机程序进行建模。在对大规模并行计算进行建模时，电路会大放异彩。例如，尼克的类或NC包含可以使用多项式数量的处理器“快速”（多对数时间）解决的问题。