1樓：
A-complete 的定義對於所有 class 都一樣, 就是說 class A (NP) 中的所有問題都可以規約到某個特定問題 (3-SAT). 想看書去找 Sipser, 或者 Arora&Barak, 或者 Goldreich, 或者 Papadimitriou.
至於 PSPACE 和 coNP, 這兩個算常見的複雜性類了. 需要說明的是,PSPACE 是空間複雜性類, 與時間無關. 如果你承認 3-SAT 是 NP-complete 的話, 那麼它說的是對於所有的 assignment (取值), 存在 (exist) 一組使得 CNF formula 被滿足.
coNP-complete 的話顧名思義, 對於所有的取值(for all), CNF formula 都不能被滿足, 即 NP 的"補".
PSPACE 的話是多項式空間, PSPACE-complete 最常見的是 TQBF, 就是說還是考慮乙個 Boolean function, 不過這回對於第乙個變數的所有取值, 第二個變數存在乙個取值, 第三個變數的所有取值, ... 判斷 Boolean function 是否被滿足.
意義的話, 可以囉嗦兩句. 比如說乙個事實是 GNI (圖非同構) 有 interactive proof protocol ( ), 那麼如果 GI 是 NP-complete 的話, GNI 就是 coNP-complete. 於是有 , 這會導致 Polynomial Hierarchy 坍縮至第三層.
這事被認為和 一樣很不可能發生, 於是圖同構幾乎不可能是 NP-complete 的. 類似的 assumption 也用在了 Boson Sampling, 即逆多項式精度的 multiplicative error 下對類似 Permanent 的東西取樣如果有經典的隨機多項式時間演算法, 同樣會導致 坍縮.
2樓：
入門級，嗯
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...
演算法時間複雜度為O（n ）的是什麼演算法？
子正 O n 的演算法不稱其為演算法，它意味著這個問題尚未解決。n稍微大一點，就會耗盡CPU的算力。它比不斷摺紙 圍棋盤上擺大公尺得到的數更大。這種 演算法 是進行演算法改進的物件。演算法老師沒有花力氣說明這種演算法的荒謬之處倒是個很不可思議的事情。n 是個很大的數，你可以用windows自帶的計算...
edmonds karp 演算法的複雜度？
證明 Edmonds Karp演算法時間複雜度為 閱讀如下詳細證明的前提是你已經完全掌握了EK演算法的步驟。證明開始 參考了網上找到的 證明1 證明2 a EK演算法中一次BFS尋找增廣路的時間複雜度為 每次BFS增廣，在增廣路上的未飽和邊會多出一條反向邊，故增廣操作導致的邊數增長不會使總邊數超過原...