概念补充

NC

在计算复杂度理论中，NC（Nick’s Class）是一类并行计算的复杂度类，用来描述在并行计算机上可以高效解决的问题。更具体来说，NC类中的问题可以使用多处理器计算系统在多项式时间内完成计算，且所需的处理器数量是多项式增长的。换句话说，NC类中的问题可以在并行计算环境下有效地解决。

NC的定义如下：

  • NC = 并行算法的复杂度类，包括那些可以使用多项式数量的处理器在对数时间内解决的问题。

NC类进一步分为多个子类，基于其所需的深度（即并行计算的步骤数量），这些子类通常表示为NC^k，其中k是对数时间的上限。

NC1 是NC的一个子类，表示那些可以使用对数深度的电路（即计算步数是对数级别的）来解决的问题：

  • NC1 = 可以用对数深度电路解决的问题，这意味着这些问题可以通过并行计算在对数时间内解决。

简而言之，NC类问题可以通过并行计算有效解决，NC1则是复杂度更低的子集，问题在对数深度的电路中可解。