algorithm - 什么是电路？

Question

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

Answer 1

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

如您所见，它们派上用场的地方是确定特定问题的复杂性。 FFT 示例相当容易理解，但最著名的示例可能是 Cook 对 NP-Completeness 的定义，它证明了确定给定 bool 电路是否可满足是 NP-Complete。

Barrington 和 Maciel 有一系列的计算复杂度 lecture notes在第一讲中介绍电路并在整个过程中继续使用该概念。