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中出现。