给定一有效可逼近的几率分布
及其于某个k-限
上的密度
,并给出一个instance 以及精度参数
可以得到一个不大于
的解
,且时间复杂度是
的多项式函数。
(第四章)
与asym. optimal errCrct. code的关系[编辑 | 编辑源代码]
Alon1992 中指出的
是一个具字母数为
的键集。
- 任何子集
皆被视为(n,M)-code (n 码长、M项的编码)。
- code rate 编码效率定义为
![{\displaystyle R=R(C)\doteq \log _{q}{\frac {M}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf490651885fd9626ae2645271f9f66428c2536c)
- 一个编码
的codeword 字串
(
中每一个
的元素),其中第 i 个字母表示作![{\displaystyle x_{i\in [n]}^{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/980ebe9aa03e97113640dbb5403f7a02968ca0be)
- t-hashing:一个参数
,当某个编码
的任
个元素必存在一个位置
足以区别该
个元素,即是
,此时称该编码是一个 t-杂凑函数。
- (m,q,k)-perfect hash family是一群杂凑函数H
(t,k)-hashing是一种k限问题。
杂凑函数
可以被视为是一个字串
,
对应到
。
k个限制
,此处
。
Parent Identifying Code[编辑 | 编辑源代码]
定义如下:
- 一个(n,M)-code C的子集 X,给座标
,有 n 个projection
就是每个x第 i位置的字元集合。
- X的envelope
![{\displaystyle e(X)=\{x\in Q^{n}:\forall i,x_{i}\in P_{i}(X)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2da61dc45d4e58453dc4a67af423dbf6d8f002c3)