k-限制問題

本文主要探討關於k-限制問題(以下或簡稱k-限問題或k-限)。並主要以Alon的論文為參考對象。

定義集

符號及名詞解釋

• [x]表示 ${1,2,3...x}$
• 支集(英語：Support，記作$Supp(f)$)表示一個函數的定義域中所有$x$使得$f(x)\neq 0$。

第一章

路徑問題

在有向圖$G(V,E)$中找是否有長度為k的路徑。

定義一: k-限制問題

k-限制問題由以下兩個敘述定義：

1. 該問題的輸入為
   • 一個大小為 $q$ 的字符集 $\Sigma$
   • 一個長度 $m$
   • $s$ 個函數 $f_{i\in [s]}:\sigma ^{k}->\{0,1\}$ ，而每個函數不得為全否定函數，意即 $\forall t\in [s],\exists x\in \Sigma ^{k}\ni f_{t}(a)=1$。
2. 該問題的輸出為一個集合 $A\subseteq \Sigma ^{m}$，其中 $A$ 的成員 $a$ 滿足 $\displaystyle {\forall i_{t}\ni 1\leq i_{1}<i_{2}<\ldots <i_{k}\leq m\ \forall j\in [s],\exists a\in A\quad f_{j}(\{a_{i_{t}}\}_{t=1}^{k})=1}$

由此可知，$\Sigma ^{m}$(即A的宇集)任何必將是任意k-限問題的一個解。但該解為最大解，即任何問題的窮舉。最理想是剔除掉所有不為解的 $a$，但k-限之難度是 NP，無法於多項式時間內得到該解集合，因此該論文以機率方法將 $A$ 限縮，而解集合的好壞取決於 $A$ 的大小。即是，與集合中不為解的$a$的個數有關。

第二章

定義二：機率密度

給定任意一個機率分佈 $D:\Sigma ^{m}\rightarrow [0,1]$，一個k-限問題對於$D$之中，$a$的機率密度($D$之中抽到 $a$的機率$\varepsilon$定義為$\displaystyle {\varepsilon \doteq {\underset {\overset {i_{1}<i_{2}<\dots <i_{k}\in [m]}{j\in [s]}}{\min }}\left\{{\underset {a\sim D}{\Pr[}}\ f_{j}(a_{i_{1}}a_{i_{2}}\dots a_{i_{k}})=1]\right\}}$

可見，每個和k-限問題相關的機率分佈密度皆大於均勻分佈的密度${\frac {1}{q^{m}}}\cdot {\frac {q^{k}}{q^{m}}}=q^{-k}$。而引用以下命題可以證明當一個機率分佈中$\varepsilon$越大，$A$越小。

命題一：併集限度

對於每個k-限及於其上的密度為 $\varepsilon$ 的分佈$D$，有一個至大為${\biggr \lceil }{\frac {k\ln m+\ln s}{\varepsilon }}{\biggr \rceil }$的解。

其證明利用反證法：

設一個自然數 $t>{\frac {k\ln m+\ln s}{\varepsilon }}$ 。考慮 $A=\{a_{1},a_{2},\dots ,a_{t}\}\subseteq \Sigma ^{m}$，其中$a_{1},\dots ,a_{t}$ 各不同，分別自$D$中獨立取出。根據不等式 $1-x\leq e^{-x}$，可得：${\underset {a_{1},\dots ,a_{t}\sim D}{\Pr }}[\exists i_{[k]}\exists j\forall a\in A,f_{j}(a_{i_{1}}\dots a_{i_{k}})=0]\leq {\binom {m}{k}}\cdot s(1-\varepsilon )^{t}\leq \exp(k\ln m+\ln s-\varepsilon t)$

Moreover, picking slightly more vectors at random from D should yield a solution with high probability. But note that we do not know of an efficient way to verify a given set of vectors really does form a solution, unless k = Θ(1).

第三章

定義三：$l_{p}$-笵距離 (p-笵線性距離)

直接建構出$D$或許有些困難，但是我們可以建構出一個與其足夠接近的解。

在取樣空間$\Omega$中的兩個機率分佈$D,P$，他們的$l_{p}$-笵距離$\lVert D-P\rVert _{p}$定義為
$\lVert D-P\rVert _{p}\doteq (\Sigma _{a\in \Omega }(|D(a)-P(a)|^{p}))^{\frac {1}{p}}$

$\Omega$在k-限中爲$\Sigma ^{m}$，在其中有一機率分佈$D$，他的密度是$\varepsilon$，有一個在$\Sigma ^{k}$$D_{(i_{[k]})}(a)\doteq \Pr _{X\sim D}[\forall t\in [k],a(t)=X(i_{t})]$，若以後未特別定義則如此。

定義四：k-項,ε-相近

在取樣空間$\Sigma ^{m}$中的兩個機率分佈$D,P$，當 ${\textstyle \forall 0\leq k\leq m\ \forall i_{[k]}\in [m],||D_{i_{[k]}}-P_{i_{[k]}}||p<\varepsilon }$時，我們說二者在p-笵上的k-項是ε相近英語：k-wise ε-close in $l_{p}$-norm。

另外，一個分佈當$\forall p\forall \varepsilon$皆接近均勻分佈$U$則說他是k-項獨立。

引理一

D,P是$\Sigma ^{m}$中，$l_{1}$kε相近的兩個機率分佈，根據定義，可得${\textstyle {\biggr |}{\underset {X\sim D}{\Pr }}[f(X(i_{[k]})=1]-{\underset {X\sim P}{\Pr }}[f(X(i_{[k]})=1]{\biggr |}<\varepsilon }$
證明：

展開拆開就結束啦

第四章

定理一

證明見第五章。

定理與其證明

本部分對應到原文的第五至第八章，將以其應用問題解決之。

第五章：項鍊分割

主頁面：User:TNTErick/NlSp

在此，我們會將k-限分作數個小部分並分別解決之。根據定理二可以找得到$k\leq \omega ({\frac {\log m}{\log \log m}})$時的解，但是在此我們能夠找到... 接下來我們將運用項鍊分割來求解。

引理六：連續項鍊分割

Every interval t-coloring has a bsplitting of size (b − 1)t. Let us describe the intuition behind the case of t = b = 2, which provides some insight to the role of topology in the proof. Call one of the types red. Instead of observing some coloring of the unit interval, observe the equivalent coloring of the one-dimensional sphere (a necklace closed at its clasp). Consider some half necklace. If the measure of red within this half is exactly 1 2 , this induces a fair partition, and we are done. Otherwise, assume without loss of generality that this measure is larger than 1 2 . When rotating the necklace 180◦ , the measure of red in the observed half is hence smaller than 1 2 . As the change in the measure is continuous, there must be a half in which this measure is exactly 1 2 . In general, the proof uses a generalization of the Borsuk-Ulam theorem.

t pairwise disjoint subsets t個兩兩不相交的子集。

第七章：廣義雜湊

傳統上的完全雜湊 (m,q,k)-Perfect Hashing指的是將$m$個元素雜湊至$q$格的雜湊表的數個雜湊函數，其中必有至少一個雜湊函數對$[m]$之中任k個的雜湊值皆不相同。

雜湊表

	i=	1	2	3	...	m

這種雜湊其中的一個推廣是廣義雜湊 (t,u)-Hash Families在#Alon2003中出現。