在可計算性理論跟計算複雜度理論內，RE（Recursively Enumerable，參考遞歸可枚舉集合）是一個決定型問題的複雜度類。裡面的問題，當答案是"yes"的時候可以使用圖靈機在有限的時間內運算。[1]不大正式的說法是，當問題的答案是"yes"，則存在一些方法可以在有限時間內決定。不過，如果這個問題的答案是"NO"，那這個機器有可能永遠沒有辦法結束運算。RE也可以視為存在一個將問題裡面"yes"的答案一一列舉出來的圖靈機（也就是這裡所說'可枚舉的'的意思）。
co-RE則是所有RE語言其補集（complement）的總集合。某種意義上我們可以說，co-RE包含的語言，其裡面的問題要證明為錯誤，只要有限的時間；但是可能要無限的時間，才能證明這問題正確。
Immerman–Szelepcsényi定理則指出對任何s(n) ≥ log n，NSPACE(s(n))在補集運算下封閉(closed under complement)。 NSPACE可以與DTIME作連接如下： 對任何space constructible function s(n), NSPACE (
1007/3-540-10003-2_85 Nisan, Noam; Ta-Shma, Amnon, Symmetric logspace is closed under complement, Chicago Journal of Theoretical Computer Science, 1995, Article 1, MR 1345937
nonisomorphism problem），即圖同構問題（英语：graph isomorphism problem）之補（英语：complement (complexity)），有零知識證明。該問題已知屬於反NP，但未知是否屬於NP或其他實際可行的複雜度類。更一般地，羅素·英帕利亞佐（英语：Russell
Architectures Software Developer's Manual, Signed integers are two's complement binary values that can be used to represent both positive and negative
biological plausibility, assessment reliability and clinical effectiveness. Complement Ther Med. 1999, 7 (4): 201–7. PMID 10709302. doi:10.1016/S0965-2299(99)80002-8
dna_sequence[2:7] Seq('GCTTC', IUPACUnambiguousDNA()) >>> dna_sequence.reverse_complement() Seq('TACGAGAAGCCT', IUPACUnambiguousDNA()) >>> rna_sequence = dna_sequence
Maehara, Hiroshi, Planar unit-distance graphs having planar unit-distance complement, Discrete Mathematics, 2008, 308 (10): 1973–1984, doi:10.1016/j.disc.2007
