[x]表示
1
,
2
,
3...
x
{\displaystyle {1,2,3...x}}
支集 (英语：Support ，记作
S
u
p
p
(
f
)
{\displaystyle Supp(f)}
x
{\displaystyle x}
f
(
x
)
≠
0
{\displaystyle f(x)\neq 0}
在有向图
G
(
V
,
E
)
{\displaystyle G(V,E)}
k-限制问题 由以下两个叙述定义：
该问题的输入为
一个大小为
q
{\displaystyle q}
Σ
{\displaystyle \Sigma }
一个长度
m
{\displaystyle m}
s
{\displaystyle s}
f
i
∈
[
s
]
:
σ
k
−
>
{
0
,
1
}
{\displaystyle f_{i\in [s]}:\sigma ^{k}->\{0,1\}}
∀
t
∈
[
s
]
,
∃
x
∈
Σ
k
∋
f
t
(
a
)
=
1
{\displaystyle \forall t\in [s],\exists x\in \Sigma ^{k}\ni f_{t}(a)=1}
该问题的输出为一个集合
A
⊆
Σ
m
{\displaystyle A\subseteq \Sigma ^{m}}
A
{\displaystyle A}
a
{\displaystyle a}
∀
i
t
∋
1
≤
i
1
<
i
2
<
…
<
i
k
≤
m
∀
j
∈
[
s
]
,
∃
a
∈
A
f
j
(
{
a
i
t
}
t
=
1
k
)
=
1
{\displaystyle \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}}
由此可知，
Σ
m
{\displaystyle \Sigma ^{m}}
宇集 )任何必将是任意k-限问题的一个解。但该解为最大解，即任何问题的穷举 。最理想是剔除掉所有不为解的
a
{\displaystyle a}
NP ，无法于多项式时间内得到该解集合，因此该论文以机率方法 将
A
{\displaystyle A}
A
{\displaystyle A}
a
{\displaystyle a}
给定任意一个机率分布
D
:
Σ
m
→
[
0
,
1
]
{\displaystyle D:\Sigma ^{m}\rightarrow [0,1]}
D
{\displaystyle D}
a
{\displaystyle a}
D
{\displaystyle D}
a
{\displaystyle a}
ε
{\displaystyle \varepsilon }
ε
≐
min
j
∈
[
s
]
i
1
<
i
2
<
⋯
<
i
k
∈
[
m
]
{
Pr
[
a
∼
D
f
j
(
a
i
1
a
i
2
…
a
i
k
)
=
1
]
}
{\displaystyle \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-限问题相关的机率分布密度皆大于均匀分布的密度
1
q
m
⋅
q
k
q
m
=
q
−
k
{\displaystyle {\frac {1}{q^{m}}}\cdot {\frac {q^{k}}{q^{m}}}=q^{-k}}
ε
{\displaystyle \varepsilon }
A
{\displaystyle A}
对于每个k-限 及于其上的密度为
ε
{\displaystyle \varepsilon }
D
{\displaystyle D}
⌈
k
ln
m
+
ln
s
ε
⌉
{\displaystyle {\biggr \lceil }{\frac {k\ln m+\ln s}{\varepsilon }}{\biggr \rceil }}
其证明利用反证法 ：
设一个自然数
t
>
k
ln
m
+
ln
s
ε
{\displaystyle t>{\frac {k\ln m+\ln s}{\varepsilon }}}
A
=
{
a
1
,
a
2
,
…
,
a
t
}
⊆
Σ
m
{\displaystyle A=\{a_{1},a_{2},\dots ,a_{t}\}\subseteq \Sigma ^{m}}
a
1
,
…
,
a
t
{\displaystyle a_{1},\dots ,a_{t}}
D
{\displaystyle D}
1
−
x
≤
e
−
x
{\displaystyle 1-x\leq e^{-x}}
Pr
a
1
,
…
,
a
t
∼
D
[
∃
i
[
k
]
∃
j
∀
a
∈
A
,
f
j
(
a
i
1
…
a
i
k
)
=
0
]
≤
(
m
k
)
⋅
s
(
1
−
ε
)
t
≤
exp
(
k
ln
m
+
ln
s
−
ε
t
)
{\displaystyle {\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
{\displaystyle l_{p}}
编辑
直接建构出
D
{\displaystyle D}
在取样空间
Ω
{\displaystyle \Omega }
D
,
P
{\displaystyle D,P}
l
p
{\displaystyle l_{p}}
‖
D
−
P
‖
p
{\displaystyle \lVert D-P\rVert _{p}}
‖
D
−
P
‖
p
≐
(
Σ
a
∈
Ω
(
|
D
(
a
)
−
P
(
a
)
|
p
)
)
1
p
{\displaystyle \lVert D-P\rVert _{p}\doteq (\Sigma _{a\in \Omega }(|D(a)-P(a)|^{p}))^{\frac {1}{p}}}
Ω
{\displaystyle \Omega }
k-限 中为
Σ
m
{\displaystyle \Sigma ^{m}}
D
{\displaystyle D}
ε
{\displaystyle \varepsilon }
Σ
k
{\displaystyle \Sigma ^{k}}
D
(
i
[
k
]
)
(
a
)
≐
Pr
X
∼
D
[
∀
t
∈
[
k
]
,
a
(
t
)
=
X
(
i
t
)
]
{\displaystyle D_{(i_{[k]})}(a)\doteq \Pr _{X\sim D}[\forall t\in [k],a(t)=X(i_{t})]}
在取样空间
Σ
m
{\displaystyle \Sigma ^{m}}
D
,
P
{\displaystyle D,P}
∀
0
≤
k
≤
m
∀
i
[
k
]
∈
[
m
]
,
|
|
D
i
[
k
]
−
P
i
[
k
]
|
|
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
{\displaystyle l_{p}}
。
另外，一个分布当
∀
p
∀
ε
{\displaystyle \forall p\forall \varepsilon }
U
{\displaystyle U}
k-项独立 。
D,P是
Σ
m
{\displaystyle \Sigma ^{m}}
l
1
{\displaystyle l_{1}}
|
Pr
X
∼
D
[
f
(
X
(
i
[
k
]
)
=
1
]
−
Pr
X
∼
P
[
f
(
X
(
i
[
k
]
)
=
1
]
|
<
ε
{\textstyle {\biggr |}{\underset {X\sim D}{\Pr }}[f(X(i_{[k]})=1]-{\underset {X\sim P}{\Pr }}[f(X(i_{[k]})=1]{\biggr |}<\varepsilon }
展开拆开就结束啦
证明见第五章。
本部分对应到原文的第五至第八章，将以其应用问题解决之。
在此，我们会将k-限 分作数个小部分并分别解决之。根据定理二可以找得到
k
≤
ω
(
log
m
log
log
m
)
{\displaystyle 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
{\displaystyle m}
q
{\displaystyle q}
[
m
]
{\displaystyle [m]}
这种杂凑其中的一个推广是广义杂凑 (t,u)-Hash Families 在#Alon2003 中出现。
![{\displaystyle f_{i\in [s]}:\sigma ^{k}->\{0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3eb89e6c42a5e94957d845c7cc6740654e36f267)
![{\displaystyle \forall t\in [s],\exists x\in \Sigma ^{k}\ni f_{t}(a)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea50cf95baf712f4f791c5d320310aa63e28416f)
![{\displaystyle \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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dd24265c9b6d11ad605336c61bb3416248f5a01)
![{\displaystyle D:\Sigma ^{m}\rightarrow [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/252a5df6b0572a7e10f3cde99debe8ad38831631)
![{\displaystyle \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\}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba3396e322fab5c3ea60d8d732b84df18fb026c)
![{\displaystyle {\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6215518b0c06ff54480e6981708816245b1757e4)
![{\displaystyle D_{(i_{[k]})}(a)\doteq \Pr _{X\sim D}[\forall t\in [k],a(t)=X(i_{t})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/334cf90690246bbf6f46756216f627cd88c26f36)
![{\textstyle \forall 0\leq k\leq m\ \forall i_{[k]}\in [m],||D_{i_{[k]}}-P_{i_{[k]}}||p<\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/197005fa3d9045e40818c7b8741bb8fe0c975a58)
![{\textstyle {\biggr |}{\underset {X\sim D}{\Pr }}[f(X(i_{[k]})=1]-{\underset {X\sim P}{\Pr }}[f(X(i_{[k]})=1]{\biggr |}<\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3218e152421fec21fe9be0cefcdbbb2479c131f5)
![{\displaystyle [m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b649f5418f2ac84d66063f41319368b0926ccec4)