Valiant Vazirani Theorem 中文簡介

Valiant  Vazirani Theorem
這也是個很玄的定理，網路應該上找不到中文介紹，敝人小嫩嫩來寫一篇，
wiki 介紹:
https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem.

簡單說:
大家知道 SAT 是 NP complete.
意思是 給一個 circuit. 問他有沒有解，這問題是 hard 屬於所有np complete 最難的。
那如果我們給點條件，
假設 我已經保證給你這個 formula SAT 只有兩種可能，一種是沒有解，一種是只有一個解。
然後你告訴是我哪一種????
這問題照定義: 肯定比 SAT 簡單~~ 因為如果 我知道後者，肯定知道前者。SAT 如果有解，不一定只有一個解，但我現在限制有解的情況下，只有1種解。
問題是: 真的嘛???
這問題有沒有真的比 SAT 簡單????

Valiant  Vazirani Theorem 說: 沒有XD
結論是:他們一樣困難。證明想法是: 給一個SAT 製造出 很多circuit  c1, c2, c3.......c_n

製造出這些傢伙，只要多項式時間。
Valiant  Vazirani  proof: 如果SAT 無解，則c1, c2, c3.......c_n 沒有任何一個有解。 如果SAT 有解，則c1, c2, c3.......c_n其中有一個 有很大的機率有只有一個解。

相信大家看完這定理的論述。就知道為何這問題有沒有真的比 SAT 簡單。


從這裡可以製造出更多奇怪的class, 和一些更複雜，更weird的class. 像是 #P, parity P。我看線上課程，做了一些筆記，
後面就是 得到圖靈獎的大定理了。

Toda's  Theorem

Go back to Main page Notes for Complexity theory