計算復雜性理論的研究對象是算法在執行時所需的計算資源，而為了討論這壹點，我們必須假設算法是在某個計算模型上運行的。常討論的計算模型包括圖靈機（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）。