什么是电路？

Question

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

Answer 1

有些问题容易解决，有些问题很难解决。为了说明是什么使问题变得容易，是什么使问题变得更加困难，我们通常使用计算机模型，并在这些模型上设置约束。

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

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

图灵机用于模拟单线程计算机程序。当大规模并行计算建模时，电路就会发光。例如，Nick的类或NC包含可以用多项式数的处理器“快速”解决的问题(多日志时间)。