1樓：
先考慮兩類常見的問題：搜尋型問題和判定型問題。搜尋型問題對應於乙個關係R，判定型問題對應於乙個集合S。
Cook歸約對這兩類問題都有效；Karp歸約只能應用於判定型問題，歸約的物件是集合與集合；Levin歸約只能應用於搜尋型問題，歸約的物件是關係與關係。事實上，Levin歸約是為了特地處理搜尋型問題，根據Karp歸約來定義的。
2樓：Climber.pI
我感覺 Karp reduction 和 Cook reduction 的區別還是比較好解釋的, 雖然前幾年看到這些東西的時候是有點困惑.
譬如說你想證明某個問題 A 是 NP-hard 的, 那麼就假定你有求解這個問題對應的語言 L 的 oracle. 為了證明 NP-hardness, 你需要通過查詢這個 oracle 來求解 NP 中的任何問題, 而你能用的就是一台確定性多項式時間的機器, 所以現在的問題是你允許怎麼查詢這個 oracle:
只能呼叫 oracle 一次, 這就是 Karp reduction.
可以 non-adaptive 地 (並行地) 查詢 oracle 多項式次這就是 truth-table reduction.
可以 adaptive 地 (一次接一次地) 查詢 oracle 多項式次, 這就是 Cook reduction.
為什麼上面的三種 oracle 呼叫方式不一樣呢? 不妨假設這個問題 A 其實是 NP-complete 的, 那麼上述三種查詢方式對應的複雜性類分別是 , 而這三個複雜性類不太可能發生 collapse. 不難看到一些簡單的區別:
大多數人相信 NP 對補不封閉, 即 , 公鑰密碼學中作為困難假設的幾個問題 (包括 factoring 和格密碼相關的) 都在 裡. 注意到 , 那麼 會推出 NP 對補封閉, 所以這兩個複雜性類不太可能 collapse.
我們知道 NP 求解的是判定問題, 如果這個問題在 YES case, 那麼我們能夠找到乙個 NP 問題的 instance 的 witness 嗎? 通過一次查詢 oracle 顯然不夠, 標準做法是 adaptive 地查詢 oracle 多項式次 (即乙個位元乙個位元的猜測 witness 到底是什麼, 這稱作 search-to-decision reduction, 之前在 Stack Exchange 上寫過乙個更詳細的回答: Self reducibility of QCMA problems).
Levin reduction 我不太熟悉, 按照 Arora-Barak 的說法, 還對規約前後的 witness 的大小有要求 (要求都是多項式的). Arora-Barak 舉得例子是 PCP reduction, 這裡不再展開.
然後舉一些 Karp reduction, truth-table reduction, Cook reduction 對於不同複雜性類的例子吧.
QMA, 即 NP 的 quantum analog:
考慮這麼乙個問題, 假設有乙個多項式個量子位元的量子態 , 不過你只能拿到從這個態得到的若干個約化密度矩陣 (local density matrices), 能不能判斷這些約化密度矩陣都是來自這個量子態 的呢? 這個問題的 QMA-hardness 證明最早 (2006 年) 用的是 Cook reduction [1], 直到兩個月前大家終於搞清楚了怎麼用 Karp reduction 證明 [2].
此外, 如果我們按照上述三種 oracle 查詢方式定義 QMA 的變種的話, 那麼 , 也就是說和 NP 類似. 假設 QMA 不對補封閉的話, 我們可以得到類似的結果 [3], 即 比 QMA 稍微大一點. 中間的等號的證明也是很近的結果, 見 [4].
2. PP, 即 NP 的計數 (判定) 版本:
NP 的非確定性圖靈機定義告訴我們, 如果乙個問題在 NP 裡, 那麼我們可以找到乙個解. 如果我們想數到底有多少個解的話, 那麼對應的複雜性類是 #P. 如果我們想知道解的個數是大於還是小於某個確定的數 (比如所有計算分支的數量的一半的話), 那麼對應的複雜性類是 PP.
如果我們對 PP 考慮上面三種 oracle 查詢方式的話, 那麼 . 也就是說 PP 對 truth-table reduction 封閉; 而另一方面, 儘管 #P 看起來是個比 PP 大一點的複雜性類, 但每個對 #P oracle 的查詢都可以用多項式次 PP oracle 的 adaptive query 來模擬 (做二分查詢).
3. PSPACE, 多項式空間:
我們同樣可以定義 PSPACE 在上述三種 oracle 查詢方式下的複雜性類, 但我們會得到 . 事實上, 可以證明 , 也就是說 PSPACE 不但對上述三種規約方式封閉, 甚至即使允許多項式空間規約仍然是封閉的.
參考文獻
[1] Consistency of Local Density Matrices is QMA-complete
[2] Zero-Knowledge for QMA from Locally Simulatable Proofs
[3] On physical problems that are slightly more difficult than QMA
[4] Oracle complexity classes and local measurements on physical Hamiltonians
團隊Leader 技術Leader 研發Leader，他們是同乙個職位嗎？
徐毅 19年的問題，現在都沒幾個答案，有點暈。這個問題，簡單來說和嚴格來說就是 看情況。詳細點來說呢，確實是看情況，也就是說無法泛泛而談。如果是小公司，沒必要太區分這三個角色，因為通常人不多，就幾個人，那真正的領導可能就乙個，又要當老闆又要管技術，還得是主程。這種情況下，要管人，所以是團隊leade...
如何評價 Mot rhead 主唱兼貝斯手 Lemmy Kilmister 的一生？
Ruiz 只有他能酗40年酒，嗑50年藥，睡2000個女人，70歲了還玩最躁的搖滾樂 安息忽略以上的話，就衝他帶槍花小朋友玩，我就要跪舔了。對了，槍花明年巡演 鐘澤爾 轉一條。Chazz Who d win in a wrestling match,Lemmy or God?Chris Moore ...
電腦顯示屏 backlight LED 和 LED 有區別嗎？
緬因精英 CCFL 也有好的產品，CCFL照樣可以達到125 SRGB以上的色域。渣的金屬不如好的塑料，低端的White LED，在表現上除了省電和壽命，都不會比CCFL強的。 和光 家用消費顯示屏如電腦 液晶電視所稱的LED屏，即為 backlight LED 也就是用LED作為背光源的液晶屏。在...