Friday, November 30, 2018
Thursday, November 29, 2018
杭州西湖 紅葉
杭州西湖 紅葉
想起一個苦歌:
*風風雨雨來時路 無奈轉來轉去停不住
四海五湖 洗不盡的苦 話兒沒說眼已模糊
風風雨雨來時路 無奈轉來轉去停不住
是醒也苦 是醉也苦 他日重逢天涯何處
人間悲歡離合 易如反掌 看那青山綠水 別來無恙
總是要說太長 不說太難 今生將隨風流轉
人間悲歡離合 易如反掌 看那青山綠水 別來無恙
總是要說太長 不說太難 今生將隨風流轉*
Wednesday, November 28, 2018
Ladner's Theorem 證明
Ladner's Theorem 證明
這也是一個奇怪的講題。
定理意思是 ，如果P 不等於 NP, 則存在某個問題L，不是P，也不是 NP complete.
簡單說 ，就是，他們兩個中間還有很多問題~~~。
這也是目前大家believe的結果，很多難題，像是factoring, graph isomorphism 等等問題
都被認為是這樣類型的問題。
不過要證明這定理，這裡多做一個假設叫做:
exponential time hypothesis (ETH)
意思是假設，sat ，不只沒有Polynomial time algorithm。而且只有指數型的algorithm。
不能再更小了。
如下，則可以證明:Ladner's Theorem
Go back to Main page Notes for Complexity theory
這也是一個奇怪的講題。
定理意思是 ，如果P 不等於 NP, 則存在某個問題L，不是P，也不是 NP complete.
簡單說 ，就是，他們兩個中間還有很多問題~~~。
這也是目前大家believe的結果，很多難題，像是factoring, graph isomorphism 等等問題
都被認為是這樣類型的問題。
不過要證明這定理，這裡多做一個假設叫做:
exponential time hypothesis (ETH)
意思是假設，sat ，不只沒有Polynomial time algorithm。而且只有指數型的algorithm。
不能再更小了。
如下，則可以證明:Ladner's Theorem
Go back to Main page Notes for Complexity theory
2015資訊月正妹雲集
第四年 看資訊月 感謝各位正妹show girl md給鏡頭眼神 都很美 包括:
錢錢 木子萱 子婷 艾妮塔 小蘋果 annie pan
何瑋珍 古芳如 東東 孔安 周盈欣 小蔓 Sabrina Huang ......
拍不好請見諒
有些想拍沒拍到哭哭
錢錢 木子萱 子婷 艾妮塔 小蘋果 annie pan
何瑋珍 古芳如 東東 孔安 周盈欣 小蔓 Sabrina Huang ......
拍不好請見諒
有些想拍沒拍到哭哭
還有一天 大家想去記得去喔
Tuesday, November 27, 2018
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
這也是個很玄的定理，網路應該上找不到中文介紹，敝人小嫩嫩來寫一篇，
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
Subscribe to:
Posts (Atom)