计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。常讨论的计算模型包括图灵机（Turing machine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。而计算资源与计算模型是相关的，如对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。
由邱奇-图灵论题（Church-Turing thesis），所有的一致的计算模型与图灵机在多项式时间意义下是等价的。而由于我们一般将多项式时间作为有效算法的标志，该论题使得我们可以仅仅关注图灵机而忽略其它的计算模型。 主条目：判定性问题
我们考虑对一个算法问题，什么样的回答是我们所需要的。比如搜索问题：给定数组A，和一个数s，我们要问s在不在A中（判定性问题，decision problem）。而进一步的，s如果在A中的话，s的位置是什么（搜索型问题，search problem）。再比如完美匹配问题（perfect matching）：给定一个二分图G=(V,E)，我们问是不是存在边集E，使得二分图中每个结点恰好属于该边集的一条边（判定型问题）。而进一步的，E存在的话，E具体是什么（搜索型问题）。
自然的，我们会发现对于一般的算法问题A，我们都可以这样来问：首先，解是不是存在的？其次，如果解存在，这个解具体是什么？这就是A的判定型问题和A的搜索型问题（又称函数型问题）区分来源的直观解释。对判定型问题的回答只需是“是”或“否”，而对搜索型问题，需要返回解的具体形式或者“解不存在”。所以一个对A的搜索型问题的算法自然的也是对A的判定型问题的算法。反之，给定了一个A的判定型问题的算法，是否存在A的搜索型问题的算法，在可计算性理论和计算复杂性理论中有着不同的回答，这也是理解计算复杂性理论与它的前身可计算性理论不同的一个基本的观察。
在可计算性理论中，可以说明，判定型问题和搜索型问题在可计算性的意义下是等价的（见Decision problem）。而在计算复杂性中，Khuller和Vazirani在1990年代证明了在P≠NP的假设下，平面图4-着色问题的判定型问题是在P中的，而寻找其字典序第一的着色是NP难的。
所以在可计算性理论中，只关注判定型问题是合理的。在计算复杂性理论中，虽然一些基本的复杂性类（如P，NP和PSPACE），以及一些基本的问题（P和NP关系问题等）是用判定型问题来定义的，但函数型问题复杂性类也被定义（如FP，FNP等），而且一些特别的函数型问题复杂性类，如TFNP，也正在逐渐受到关注。 上面提到计算复杂性理论的研究对象是执行一项计算任务所用的资源，特别的，时间和空间是最重要的两项资源。
我们用时间作例子来讨论算法分析的一些基础知识。如果将输入的长度（设为n）作为变量，而我们关注的是算法运行时间关于n的函数关系T(n)。因为一个算法在不同的计算模型上实现时T(n)可能会有常数因子的差别（参见可计算性理论），我们使用大O表达式来表示T(n)，这使得我们可以忽略在不同计算模型上实现的常数因子。
以搜索这个计算任务为例。在搜索问题中，给定了一个具体的数s，和长度为n的数组A（数组中数的位置用1到n作标记），任务是当s在A中时，找到s的位置，而s不在A中时，需要报告未找到。这时输入的长度即为n+1。下面的过程即是一个最简单的算法：我们依次扫过A中的每个数，并与s进行比较，如果相等即返回当前的位置，如果扫遍所有的数而算法仍未停止，则返回未找到。
如果我们假设s在A中每个位置都是等可能的，那么算法在找到s的条件下需要1/n (1+2+...+n)=n(n+1)/2n=(n+1)/2的时间。如果s不在A中，那么需要(n+1)的时间。由大O表达式的知识我们知道算法所需的时间即为O(n)。
而如果我们进一步假设A是已排序的，那么我们有二分查找算法，使得算法的运行时间是O(logn)。可以看出执行一项计算任务，不同的算法在运行时间上是有很大差异的。 将计算问题按照在不同计算模型下所需资源的不同予以分类，从而得到一个对算法问题“难度”的类别，就是复杂性理论中复杂性类概念的来源。例如一个问题如果在确定性图灵机上所需时间不会超过一个确定的多项式（以输入的长度为多项式的不定元），那么我们称这类问题的集合为P（polynomial time Turing machine）。而将前述定义中的“确定性图灵机”改为“不确定性图灵机”，那么所得到的问题集合为NP（non-deteministic polynomial time Turing machine）。类似的，设n为输入的长度，那我们可以定义“在确定性图灵机上所需空间不超O(logn）的算法问题的集合”（即为L），“存在深度为O(logn)，输入的度（fan-in）为O(1)的电路族（circuit family）的算法问题的集合”（即为NC）等等复杂性类。
定义复杂性类问题的目的是为了将所有的算法问题进行分类，以确定当前算法的难度，和可能的前进方向。这是复杂性理论的一个主线之一：对算法问题进行抽象和分类。例如通过大O表达式，我们可以对忽略因计算模型不同而引入的常数因子。而第二个重要的理论假设，就是将多项式时间作为有效算法的标志（与之对应的是指数时间）。这样，复杂性类使得我们可以忽略多项式阶的不同而专注于多项式时间和指数时间的差别。（对多项式时间作为有效算法的标志这一点是有一定争议的，比如，如果算法的运行时间n，那它也可以看作是缓慢的，见理论与实践。）在本文的其余章节，“有效算法”等价于“多项式算法” 归约（reduction）是将不同算法问题建立联系的主要的技术手段，并且在某种程度上，定义了算法问题的相对难度。简单来说，假设我们有算法任务A和B，如果我们想说“A比B简单”（记为A≤B），它应该是什么意思呢？从归约的观点来看，就是说如果我们有了B的有效算法M，那么我们有一个有效算法N，它可以引用M，最终它要解决A问题。
我们以点集覆盖问题（vertex cover）和独立集问题（independent set）为例来进行说明。这两个问题都是图论中的问题。假设给定了无向图G=(V, E)，和一个自然数k，点集覆盖问题是要找到V的子集S，使得对∀e∈E，有s∈ S，使得s∈ e，且|S|≤k；而独立集问题也是要找V的子集S，要求是∀s1, s2∈S，(s1, s2)∉ E，且|S|≤k。
一个简单的观察即是：对G=(V, E)，一个S⊂V是覆盖点集，当且仅当S在G的补图中是独立点集（而且保持集合大小）。利用这个观察，假设我们有了解决覆盖点集问题的算法M，我们设计解决独立点集的算法N如下：
算法N。输入：给定无向图G=(V, E)，自然数k；输出：一个大小≤ k的独立点集（如果存在，否则返回“不存在”）；已知：算法M，输入为(无向图G, 自然数k)，输出大小≤ k的覆盖点集，如果这样的点集存在。否则返回“不存在”；算法步骤：对G，产生G的补图G'；调用M，输入为(G', k)；如果M返回“不存在”，输出不存在。如果M返回S⊂V，输出S。可以看出若产生补图这一步是有效的，那么如果M有效，N也是有效的。一般的，如果我们有一个B有效的算法M，和利用B作为“神谕”（oracle）的解决A问题的算法N，那么如果N是有效的，则我们有有效的解决A问题的算法N'——只需将N中查询B的操作换作具体的M算法即可。而这一性质的基本解释是：将多项式的不定元用另一个多项式代替，那么得到的仍是一个多项式。
所以从归约的观点来看，下面的说法可以看作与“A比B简单”（记为A≤B）等价：
A归约到B（A reduces to B, or A is reducible to B, or A can be reduced to B）；存在通过查询B问题来解决A问题的算法（there exists an algorithm that asks oracles of B, and solves A）。
