Friday, May 18, 2007

Remark for P/poly

有兩個 equivalent definitions: (感謝 BarrosH 的提供)

  • A language L is in P/poly if there is a language A in P and a set of advice strings {a_0, a_1, …} such that |a_i| ≤ i^{O(1)} and x is in L if and only if (x, a_|x|) is in A.

  • There is a family of circuits {C_0, C_1, …} such that |C_i| ≤ i^{O(1)} and for all i and all x = x_1…x_n, x is in L if and only if C_n(x_1, … , x_n) accepts.

另外,也可參考 wikipedia 那邊的定義與Prof. Fortnow 那邊的定義

好久沒碰 computational complexity 了,感覺頭腦頓了不少。不過在與 B 大討論完後,感覺上就是說,根據每個 nonnegative integer i,我們去造一個 advice string a_i 或是 Boolean circuit C_i,只是這 string 或 circuit的大小不會太大。稱呼這些 advice strings 或 circuits 為 non-uniform,不是在於統計上的意義,而是我們無法保證在 polynomial time 內利用 a_i (resp., C_i) 去造出 a_{i+1} (resp., C_{i+1})。接下來對於 input x,我們就根據 |x| 去找對應的 advice string a_|x| 或 C_|x| 來幫忙回答問題。

B大真強,搞得蠻清楚的。而且不厭其煩地回答我的笨問題,令我真是感激不已。以後要稱他為 B 神了。

No comments: