薛西弗斯是不是快樂的 如果外界世界是不能改變

薛西弗斯是不是快樂的

如果外界世界是不能改變

台灣低薪高房價 學術界很難發揮 女生追不到

爸媽不諒解自己才華

假設外界的聲音外界的人事物 外界的環境都是你無法改變的

like 薛西弗斯

那你還能求什麼

很難想像 薛西弗斯是快樂的

 薛西弗斯 has no input 他只能一直推石頭

我在想我們的生活還是有可以改變的 就算沒有可以改變的 但還是可以接受更大的資訊量 知道更多的東西 這樣似乎腦袋裡面的東西是可以改變的

那到底是可不可以改變?

所以一個假設是  薛西弗斯是快樂的 even with no input

我也還在思考這個問題?

Handwriting Notes for Complexity theory

Handwriting Notes for Complexity theory:

This is the main page for me to collect the complexity theory note as I collected from the youtube channel。

NOte can download if you want. 


1 :隨便說 SAT 

2:Simple quantum algorithm

3:Shor's algorithm and Hidden subgroup problems 
4:Co language
5:Halting problem
6:Interactive proof and complexity
7:Approximation Algorithm for some NP complete problems
8:Fast fourier tranformation 
9:Two simple randomized algorithms 
10:Markov chain and simple random walk. 
11:Polynomial Hierarchy Complexity
12:Randomized complexity class 
13:Grover's algorithm and query complexity
14:Introduction to Complexity theory
15:Oracle turing machine and oracle complexity 
16:Valiant Vazirani Theorem 中文簡介
17:Ladner's Theorem 證明

隨便說 SAT

隨便說 SAT:

Go back to Main page Notes for Complexity theory。

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

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

Oracle turing machine and oracle complexity

Oracle turing machine and oracle complexity

這是我覺得一個很神奇的講題，主要是講，如果是世界上出現一種黑盒子，可以瞬間解決某一種問題，那這世界的計算機複雜度會如何?

這種物件叫做 oracle. 配上這種物件的 就叫做 oracle turing machine.:

首先是給定義:

研究最簡單的類型 P^NP 這個class.

Go back to Main page Notes for Complexity theory

了解 P^NP 這個 class 有多大，證明他落在polynomial hierarchy 第二層之內

Introduction to Complexity theory

Introduction to Complexity theory
這文章主要是把我之前在網路上自讀看的計算機複雜度的第一章的介紹，寫成note.
主要就是參考
Undergrad Complexity at CMU .的note 把一些筆記自己做的寫下來，當作日後參考用。
這個小主題
主要分兩段:
第一段是 一些open questions 和 complexity theory 主要探討什麼問題，主要就是計算需求的資源，像是time, space 等等，還有randomize 所能帶來的影響。

Go back to Main page Notes for Complexity theory

第二段就是介紹一些計算機問題的分類，還有一些基本的notation。希望大家開心，如果不想看，可以右轉 展場哦
點右上角的 labels，選擇展場，就有很多正妹可以看唷。不用管這些讀書什麼的。

Grover's algorithm and query complexity

在討論完 Grover's algorithm 以後，我們就可以來討論所謂的quantum computing的計算模型

query model + query complexity

Go back to Main page Notes for Complexity theory

Go back to the main quantum computing page

Randomized complexity class

Randomized complexity class

這是我之前做的一點 看網路上課程的筆記

Randomized complexity class

主要是紀錄一下 BPP, RP, ZPP....等 有趣的complexity class:

Go back to Main page Notes for Complexity theory

開始定義complexity class

介紹他們一些有趣的性質

一個小應用:

polynomial hierarchy

這篇文章，主要是想介紹很基本的complexity class. 人們叫做 polynomial hierarchy。

PH class.

這是一個可以被視為 complete generalization of P and NP, co-NP 的主題也可以給大家一個 feeling , why people believe that Factoring 這個問題不是NP complete.

儘管大家並不能證明。果然，在complexity theory的世界裡面，很少東西是可以證明的。

首先 先給定義:
Go back to Main page Notes for Complexity theory

一些基本性質: 還解釋了 why people believe that Factoring 這個問題不是NP complete.

PH complete 問題:

good reference:
Aaronson - Quantum Computing Since Democritus chap 6

Markov chain and simple random walk.

In this blog, I try to introduce the concept of Markov chain , so first, we give the definition of markov chain. And we state that every markov chain will have a fixed point.

Go back to Main page Notes for Complexity theory

Then we introduce the random walk and how to connect the  concept of Markov Chain and the random Walk. And we proof some basic facts of the expection values.

How to leave the maze without memorize anything using random walk.

附上 wiki 的 Markov Chain  inequality:

If X is a nonnegative random variable and a > 0, then the probability that X is at least a is at most the expectation of X divided by a:

 From the definition of expectation:

${\displaystyle \operatorname {E} (X)=\int _{-\infty }^{\infty }xf(x)\,dx}$

However, X is a non-negative random variable thus,

${\displaystyle \operatorname {E} (X)=\int _{-\infty }^{\infty }xf(x)\,dx=\int _{0}^{\infty }xf(x)\,dx}$

From this we can derive,

${\displaystyle \operatorname {E} (X)=\int _{0}^{a}xf(x)\,dx+\int _{a}^{\infty }xf(x)\,dx\geq \int _{a}^{\infty }xf(x)\,dx\geq \int _{a}^{\infty }af(x)\,dx=a\int _{a}^{\infty }f(x)\,dx=a\operatorname {P} (x\geq a)}$

From here it is easy to see that

${\displaystyle \Pr(X\geq a)\leq \operatorname {E} (X)/a}$

Chebyshev's inequality

這個東西也重要

for any a > 0. Here Var(X) is the variance of X, defined as:

${\displaystyle \operatorname {Var} (X)=\operatorname {E} [(X-\operatorname {E} (X))^{2}].}$

Chebyshev's inequality follows from Markov's inequality by considering the random variable

${\displaystyle (X-\operatorname {E} (X))^{2}}$

and the constant ${\displaystyle a^{2},}$ for which Markov's inequality reads

${\displaystyle \operatorname {P} ((X-\operatorname {E} (X))^{2}\geq a^{2})\leq {\frac {\operatorname {Var} (X)}{a^{2}}}.}$

This argument can be summarized (where "MI" indicates use of Markov's inequality):

${\displaystyle \operatorname {P} (|X-\operatorname {E} (X)|\geq a)=\operatorname {P} \left((X-\operatorname {E} (X))^{2}\geq a^{2}\right)\,{\overset {\underset {\mathrm {MI} }{}}{\leq }}\,{\frac {\operatorname {E} \left((X-\operatorname {E} (X))^{2}\right)}{a^{2}}}={\frac {\operatorname {Var} (X)}{a^{2}}}.}$

Two simple randomized algorithms

In this article, I introduced Two simple randomized algorithms.
one is called matrix verfication algorithm which is very powerful and remarkable.

Go back to Main page Notes for Complexity theory

The other is so called 3 cnf formula.

3 cnf is Np complete. One need brute force (2^n) to find the such solution. But if we only care about satisfy maximum number of clauses. One could use the randomized algorithm. One can satisfy 87.5% of all clauses .