Computational Complexity Introduction

Posted on In Views: Word count in article: 337 Reading time ≈ 1 mins.
本篇是计算复杂性（CS7313)的引言部分，包括四类问题以及一些课程中会用到的证明方法。

定义

计算复杂性（Computational Complexity），即使用数学方法对计算中所需的各种资源的耗费（主要是时间和空间）作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质。课程中涉及到的数学方法主要有：

  • Algebraic Method，代数方法；
  • Probalilistic Method，概率统计方法；
  • Combinatorial Method，组合方法；
  • ...

四类问题

计算复杂性中的四类问题，即求解的时间复杂度逐级递增的四类问题：

  1. P（Polynomial）问题：有多项式时间的算法，时间复杂度O(P(n))；
  2. NP（Nondeterminism Polynomial）问题：能在多项式的时间内得到个别特殊的正确解，但是不知道是否也能在多项式时间内得到所有解；
  3. NPC（Nondeterminism Polynomial Complete）问题：一类特殊的NP问题，所有的NP问题都能约化（复杂化，如用二元一次方程的方法来解一元一次方程问题）成它。那么，只要解决了这个问题，所有能约化成它的NP问题也就解决了；
  4. NP-Hard问题：所有的NP问题都能约化为NP-Hard问题，但是NP-Hard问题本身不一定是一个NP问题。换句话说，NPC问题是NP-Hard问题的子集。