1.复杂度与规模
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
多项式级的复杂度：如 O(1)，O(log(n))，O(n^a)等 ——注意它的规模n出现在底数的位置 ！
非多项式级的复杂度：如：O(a^n)和O(n!)等。
一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。注意，在某些时候，输入规模是要值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子判定素数的算法并不是多项式时间算法的原因。
如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。
2.P与NP与NPC
P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是Non-Deterministic的意思（图灵机的概念见理论计算机初步：算法和计算模型）。
脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。
很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解。
是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？
人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的NPC问题。C是英文单词“完全”的第一个字母。
一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A。
“问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。
当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。
也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。
这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP-完全问题。
NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。
直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
3.可计算与不可计算
根据图灵-丘奇论题，：
1.可计算的问题就是能被图灵机计算的问题；（图灵的定义）
2.可计算的问题就是使用lamda演算系统可以计算的问题；(丘奇的定义)
图灵丘奇论题与其说是定理，不如说是算法的定义。因为算法本身就是一个不精确的概念，到底什么是算法，以前一直没有确切的定义。而图灵-丘奇论题则从数学上给出了算法的形式定义。
图灵说：所有的图灵机能计算的问题都是有算法的（也就是可计算的），所有有算法的问题都可以用图灵机计算。这个论题本身是无法证明的，它就像物理中的光速不变定律一样，是一条自然定律，不能加以逻辑上的证明，只能用实验来检验。而目前来看，图灵命题也和光速不变一样，经得住历史和时间的检验，现在即使发展到了量子计算机，还是没有摆脱图灵机的约束，量子计算机上可计算的问题也是普通的图灵机上可计算的问题，只不过计算效率不同而已。
不可计算的问题的两个例子，一个是Pi的例子，另一个是图灵停机问题。