交互式證明（interactive proof）
一般的 NP 證明是一份靜態文件：一個強大的證明者寫下一張證書，一個快速的驗證者讀它並檢查一次。交互式證明把這封單向信件換成一場對話。一個計算能力有限卻多疑的驗證者（被允許擲硬幣），來來回回地盤問一個全能但不可信的證明者，最後決定是否被說服。神奇之處在於：這場帶有隨機性的對話，能確立遠多於任何靜態證書所能確立的事。
它如何運作、又保證什麼。證明者無限強大但可能說謊；驗證者在多項式時間內執行並提出隨機的挑戰問題。需要兩個性質。完備性：若主張為真，誠實的證明者總能讓驗證者接受。健全性：若主張為假，那麼無論多麼聰明或多麼對抗的證明者，都無法騙過驗證者接受——除了以極微小的機率。隨機性不可或缺——驗證者的問題必須不可預測，使說謊的證明者無法事先備妥答案。類別 IP 就是以這種方式可被證明的主張之集合。
里程碑式的定理，是這個領域的瑰寶之一：IP = PSPACE——交互式證明能驗證的，恰好就是用多項式記憶體可解的問題，這是個遠超 NP 的驚人龐大類別。直覺是：驗證者不可預測的挑戰，迫使證明者在一個它無法預先計算的指數大可能性空間中保持一致。這個想法孕育出兩個巨大的後代：零知識證明（在不洩漏其他任何東西的情況下說服他人某主張為真）與 PCP 定理（只讀少數幾個隨機位元就能檢查的證明）——兩者都重塑了現代密碼學與複雜度理論。
一個關於「這兩張圖不同構」的玩具交互式證明：驗證者私下挑兩張圖中的一張，隨機打亂它的頂點，把結果出示給證明者，問「這原本是哪一張？」。若兩張圖真的不同，全能的證明者總能分辨並答對；若它們其實相同，證明者只能猜，僅一半時候答對。重複進行便把作弊者的成功率推向近乎零。
一個多疑、擲硬幣的驗證者盤問全能的證明者；隨機性封死了事先編好的謊言。
證明者擁有無限能力無妨，因為健全性保護了驗證者：即使是無限聰明的作弊者，也無法「證明」一個假主張，除非以可忽略的機率。拿掉驗證者的隨機性，這個系統就塌回普通的 NP。