Finite Playground

To verify is human; to prove, divine.


Leave a comment

MA-SETH is false

Ryan Williams just posted a new paper Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation on ECCC, in which he disproves the MA analog of the Strong Exponential Time Hypothesis (MA-SETH), which is motivated by the paper Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility by Carmosino, Gao, Impagliazzo, Mikhailin, Paturi, and Schneider, proving that assuming Nondeterministic Strong Exponential Time Hypothesis (NSETH) then some problems like 3SUM and APSP cannot be SETH-hard.

 


Leave a comment

Isolation Lemma

Isolation

這段時間在學習一個好用的技巧 – Isolation Lemma. 當我們需要在一個圖中找到特定的結構 (例如一個 perfect matching), 有時直接去找不是那麼容易; 藉由孤立 (isolation) 出某一個特定的 minimum weighted matching, 我們就能很快的找到它. 最有名的使用就是在 [MVV87] 中 Mulmuley, Vazirani 和 Vazirani (你沒看錯) 藉由證明了最初 Isolation Lemma 的雛形而得到的 perfect matching\mathsf{NC}(平行) 演算法.

在此我們介紹兩種不同的改良版: 一種是後來被 [RA00] 使用, Reinhardt 和 Allender 證明了\mathsf{NL/poly} = \mathsf{UL/poly}; 此種方法的特點是得到的 bound 很好, 但是是非建構式的. 而另一種類似 hash 的方式則是被 [CRS93] 使用, 改進了當初 [MVV87] 的演算法而得的\mathsf{NC^2}perfect matching 演算法; 後面這種方法 weight 是建構式的, 可以直覺的看出為何它能夠把所有東西分開, 但是要用到少許的 randomization. (嚴格來說, 我們真正要使用第一種方式時, 還是有 randomized 的精神在裡頭.)

首先我們來看第一個形式的 Isolation Lemma.

Theorem 1.U為一大小為n的集合, 而\mathcal{F}_1, \ldots, \mathcal{F}_m為一族非空集合, 其中每一\mathcal{F}_iU的子集所形成的集合. 令d為重量的上限, 而W為所有重量不超過d的重量函數w: U \rightarrow [d]^n形成的集合. 若我們給定一參數0 < \alpha < 1使得\alpha > mn/d, 則至少有(1-\alpha)|W|的重量函數會使得每個\mathcal{F}_1, \ldots, \mathcal{F}_m中正好都只有一個最小重量的U子集.

看起來很複雜. 我們令m=1, d=2n\alpha = 1/2來觀察這個定理看看.

Theorem 1′.U為一大小為n的集合, 而\mathcal{F}為一非空集合, \mathcal{F}中每一元素為U的子集. 均勻獨立的在U上隨機給定[2n]內的重量. 則至少有1/2的機率會使得\mathcal{F}中正好只有一個最小重量的U子集.

這樣就好懂多了; 藉由隨機給定一些不大的重量, 很容易能夠使得\mathcal{F}中有個最小元素被孤立出來. 如果不要限制重量的大小, 這其實不是很困難; 只要對U中的元素u_1, \ldots, u_n分別給予重量2^1, \ldots, 2^n就行了. 不難根據二進位表示看出U中的元素都會有不同的重量. 重點在於, 這樣的重量是指數成長的, 而多數演算法的應用只能限制在多項式成長率下. 這時藉由一點點的隨機性, 就能夠達成這樣的目標, 這是 Isolation Lemma 的厲害之處!

來看一個實際的例子好了. 在 [RA00] 的證明當中, 他們用 Isolation Lemma 孤立出圖中某兩點之間的某條路徑. 因為對任意圖來說兩點間的路徑最多會有 exponential 那麼多, 所以我們需要借助 Isolation Lemma.

[p]為圖中的點集, U為圖中的邊集, \mathcal{F}_i為點1到點i所有路徑的集合. (注意我們將路徑視為邊集的子集.) 因為|U| = n = p(p-1)(有向邊), 我們令m=p, \alpha = 1/2, d=2p^3 > mn/\alpha. 因此根據 Theorem 1, 我們可以證明底下的推論:

Corollary.G為一p點有向圖, 而W為所有重量函數w: E(G) \rightarrow [2p^3]^n形成的集合. 則至少有|W|/2的重量函數會使得對於所有i, 點1到點i的最小重量路徑是唯一的.

為什麼需要這麼多的重量函數呢? 因為我們可以藉此證出更厲害的推論:

Corollary.W為所有重量函數w: E(G) \rightarrow [2p^3]^n形成的集合. 則存在w_1, \ldots, w_{p^2} \in W個重量函數會使得對於所有p點有向圖G, 一定有一個w_k使得在G種任意點1到點i的最小重量路徑是唯一的.

Proof. 對任意一張圖, p^2個重量函數都無法估立出最短路徑的機率是2^{-p^2}. 而p個點的有向圖共有2^n = 2^{p(p-1)}個, 因此p^2個重量函數都無法孤立出某一張p點有向圖的最短路徑的機率是

2^{-p^2} \cdot s^{p(p-1)} < 1,

因此存在某個重量函數不管什麼樣的p點有向圖都能夠孤立出其最短路徑. \Box

注意後面這個推論的重點: 那p^2個重量函數是對所有p點的有向圖都適用的, 因此我們可以把這些重量函數事先寫進程式當中, 每當輸入一個圖我們就拿其中一個重量函數來孤立出最短路徑. 如果不使用這種方式, 我們就要在程式執行過程中隨機的產生一些重量函數, 給定了一個圖, 我們需要

n\log p = O(p^2 \log p)

個 random bits 來產生一組重量函數.

接下來我們來看第二種方法.

前面提到如果不限制重量的大小, 只要對U中的元素給予重量2^1, \ldots, 2^n就好了. 第二個方法利用中國剩餘定理很輕易的將重量作一些改變而壓在多項式大小, 因此這樣的方法式建構式的. 我們回到只有一個\mathcal{F}的狀況, 這次我們利用\mathcal{F}內子集的數量來減少 random bits 的使用.

Theorem 2.U為一大小為n的集合, 而\mathcal{F}為一非空集合, \mathcal{F}中每一元素為U的子集. 存在一種使用O(\log|F| + \log n)個 random bits 的方式在U上給定[n^7]內的重量, 使得至少有1/4的機率會使得\mathcal{F}中正好只有一個最小重量的U子集.

最糟糕的狀況下|F| = 2^n, 因此使用的 random bits 會是O(n + \log n), 比前一種方法好; 當|F|更小的時候 (如|F|是多項式大小), 我們甚至只需要至多$latex O(\log n)$ bits 就夠了. 完整的證明請見 [CRS93]. 不過事實上如果|F|只有多項式大小, 我們其實可以連 random 都不要用! 這在 [PTV10] 裡被拿來用以證明\mathsf{RFewL} \subseteq \mathsf{UL}, 管它這兩個莫名其妙的東西是什麼.

Theorem 2′.U為一大小為n的集合, 而\mathcal{F}中有至多f(n) = O(n^c)U的子集S_1, \ldots, S_{f(n)}. 存在一種在U上給定多項式大小的重量, 使得\mathcal{F}中正好只有一個最小重量的U子集.

Proof. 首先我們給U中的每個元素u_i重量2^i. 然後我們來看底下這個多項式:

\Delta = \prod_{1 \leq i < j \leq f(n)} (w(S_i) - w(S_j)),

這個多項式的特色就是: 當重量函數w能讓所有\mathcal{F}中的元素重量都不一樣時, 這個判別式\Delta就會不為零. \Delta值的範圍會是\delta = (2^{n+1})^{f^2(n)}. 因此我們選出從2開始的s個質數p_1, \ldots, p_s, 使得它們相乘超過\delta = (2^{n+1})^{f^2(n)}. 換句話說,

\Delta \neq 0 \mod \prod_{i=1}^s p_i.

根據質數定理,

\log \prod_{i = 1}^s p_i = s + o(s) > \log \delta = (n+1)f^2(n),

f(n) = O(n^c)時我們只要有s = n^{2c+1}就夠了. 這時中國剩餘定理告訴我們, 因為\Delta \neq 0 \mod \prod_{i=1}^s p_i, 所以一定有一個p_i使得\Delta \neq 0 \mod p_i. 最後我們只要令新的重量函數為w^*(S) = w(S) \mod p_i就行了, 根據對質數大小的估計,

p_i \leq p_s \leq s\log s \leq n^{2c+2},

因此這個重量函數只有多項式的大小而已. 因為\Delta \neq 0 \mod p_i, 所有\mathcal{F}中的元素重量都不一樣, 滿足我們對定理的需求. \Box

最後有一些後記. Isolation Lemma 使用上需要 randomized, 因為\mathcal{F}在最糟的狀況下會有2^n個元素, 因此完全的 derandomized 是不可能的. 不過針對\mathcal{F}的特性 (例如前面舉的最短路徑的例子), 有些人致力於 derandomize 相關的結果, 也有不少成果. 希望未來能看到 Isolation Lemma 更多的應用!

References.
[MVV87] Matching is as easy as matrix inversion. K. Mulmuley, U. Vazirani and V. Vazirani.
[CRS93] Randomness-optimal unique element isolation, with applications to perfect matching and related problems. S. Chari, P. Rohatgi and A. Srinivasan.
[RA00] Making nondeterminism unambiguous. K. Reinhardt and E. Allender.
[PTV10] On the power of unambiguity in logspace. A. pavan, R. Tewari and N. V. Vinodchandran.


Leave a comment

NEXP do not have ACC0 circuits

幾乎所有重要的 Complexity Theorists 的部落格上都有這條新聞…

簡單來說, Ryan Williams 在 11/8 證明了關於 circuit lower bound 的新結果:

\mathsf{NTIME}(2^n)不能用\mathsf{ACC}^0circuits – 也就是 constant-depth, poly-size circuits with AND, OR, NOT, and Mod_m gates for any m 解掉.

這個結果有多大呢? 說大也不大, 因為人們相信就連\mathsf{NP} – 比 \mathsf{NTIME}(2^n)小太多的問題集合都不可能被 poly-size circuits – 比\mathsf{ACC}^0大太多的 circuits 解掉. 換句話說, 離\mathsf{P} \neq \mathsf{NP}還有很遠.

可是那又如何? 這可是一個新的 lower bound 結果! 上過 complexity 就知道 lower bounds 有多麼難得到… 在 Ryan Williams 之前, 我們連\mathsf{NTIME}(2^n) 能不能用 constant-depth, poly-size circuits with Mod_6 gates (沒有 AND 跟 OR!!) 解掉都不知道!!

另外, 它使用的技巧也很符合之前 Ketan Mulmuley 提出的 GCT 計畫中, 用 “證明上界” 來 “證明下界” 的概念. 在這篇突破性的論文中有使用到 Ryan 自己在 STOC ’10 中的論文 “Improving exhaustive search implies superpolynomial lower bounds“. 這使得這個方向的研究又再一次活過來了, 尤其是當有二三十年 circuit lower bound 沒有新的眾大突破結果下, 大家慢慢對 circuits 失去信心時…

有興趣的除了看上面的網誌介紹之外, 趕緊看看 Ryan Williams 的論文, 這應該是繼 Reingold 的 undirected reachability in \mathsf{L}之後, 最重大的結果!!


4 Comments

Exponential Time Hypothesis

今天要介紹的東西是因為想著其他的問題時間接學到的. 考慮底下這樣的問題:

k-path Problem. 判斷一張無向圖G中有沒有一條長度大於k的 path?

看起來很單純. 我們想要討論這個問題的時間複雜度: 請問k的大小會對問題的難度造成什麼樣的影響? 首先我們可以觀察到當k=O(1)時, 一定會有一個 poly. time 的演算法, 簡單來說就是暴搜過所有k個點的子集合, 檢查它們有沒有形成一條 path. 事實上, 在 Alon, Yuster & Zwick 的經典論文 “Color-coding” 當中, 就給出了O(M(n) \log n)的演算法, 能夠判斷圖中有沒有長度為某一固定k=O(1)的 path; 時間中的M(n)n \times n矩陣相乘的時間, 與k完全無關. 在同一篇論文中, 其實對於k=O(\log n)長度的 path 也是能在 polynomial time 內找到的, 因為其實真正的時間長相是類似O^*(c^k)這樣. (O^*()記號會吃掉所有多項式時間的部分!) 另一方面, 當k=n時就變成了鼎鼎有名的 Hamiltonian path 問題, 我們都知道這是\mathsf{NP}-complete, 假設\mathsf{P} \neq \mathsf{NP}的話, 是不會有 polynomial time 演算法的. 因此問題就來了:

如果我們想要解稍微大一點的k-path problem, 例如k=O(\log^2 n), 有可能有多項式時間演算法嗎?

經過一陣網路上的詢問, 答案似乎是 NO. 要怎麼說明這件事呢? 我們要用到 complexity 理論裡的另一個猜想, 由 Impagliazzo 和 Paturi 在 2001 年的論文中提出的:

Exponential Time Hypothesis (ETH). 3-SAT 問題不能在2^{o(n)}內解掉.

這個猜想是怎麼回事呢? 我們都知道\mathsf{NP}-complete 問題能在 exponential time 解掉, 也就是O(2^{\delta n}), 對於某個\delta > 0. (基本上就是暴搜!) 但是說不定有些問題能夠在比 polynomial time 慢一些, 但比 exponential time 快一些的時間內解掉, 像是O(2^{\sqrt{n}})之類的. 這個猜想下了一記重擊: 很多能被 3-SAT reduce 到的問題, 是都沒有 sub-exponential time 演算法的!! (注意這裡的 reduction 需要比當初證明\mathsf{NP}-hard 的 reduction 再強一點, 要保持 sub-exponential time 的性質) 因此很明顯的證明 ETH 會間接證明了\mathsf{P} \neq \mathsf{NP}. (prove it!)

所以這跟我們的k-path 問題有什麼關係呢? 我們可以證明若是對於\omega(\log n)-path 問題有個 polynomial time 解的話, 會違反 ETH!! 為了說明方便, 假設我們有個 polynomial time 演算法A能解\log^2 n-path 問題好了. 根據 ETH, 我們可以證明 Hamiltonian path 也不能在2^{o(n)}內解掉. 而現在若有一張圖我們想要找 Hamiltonian path, 我們先加上很多孤立點, 使得總點數有m = 2^{\sqrt{n}}這麼多; 這時我們用演算法A\log^2 m = n-path 問題. 因為加上去的點都是孤立點, 所以如果找到了n-path 表示原先圖中有 Hamiltoniam path. 而因為演算法A是個多項式時間演算法, 我們花了O(m^c) = O(2^{c\sqrt{n}})的時間解了 Hamiltonian path 問題, 因此違反了 ETH; 所以我們證明了\log^2 n-path 問題是不能多項式時間解掉的. 同樣的理由對於任何\omega(\log n)-path 問題, 上面的敘述都保證不會有多項式時間解.

所以, 對於k-path problem, 我們有個很棒的分界點: 當k = O(\log n), 我們有多項式時間演算法; 當k = \omega(\log n), 若 ETH 為真, 則不存在多項式時間演算法. 因此有了 ETH 世界變得很簡單! 而 ETH 還有很多的用法, 在 parametrized complexity 以及 approximation algorithm 的 lower bounds 都有用途, 以後慢慢學習!