複雜度類列表

許多複雜度類都有一個前面加上'Co'的同伴，這是包含原來複雜度類裡面所有問題的補集的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。）

一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題。此外，歸約過程本身是這個複雜度或者比他更簡單的問題類別裡面。

如果找不到想要看的複雜度類（例如說找不到Co-UP），那可以尋找看看這一個類別的同伴（以剛剛的例子來說：UP）來參考。

參考資料
外部链接

• [https://web.archive.org/web/20100726082118/http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo] - list of over 400 complexity classes and their properties