给定一有效可逼近的几率分布 
及其于某个k-限 
上的密度 
，并给出一个instance 以及精度参数
可以得到一个不大于
的解
，且时间复杂度是
的多项式函数。
(第四章)
与asym. optimal errCrct. code的关系
[编辑 | 编辑源代码]Alon1992 中指出的
是一个具字母数为
的键集。- 任何子集
皆被视为(n,M)-code (n 码长、M项的编码)。
- code rate 编码效率定义为
- 一个编码
的codeword 字串![{\displaystyle x^{j\in [M]}\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/260cea8ce8bc4ddc2ddc749c1fcfa82f6707dfc3)
(中每一个
的元素)，其中第 i 个字母表示作![{\displaystyle x_{i\in [n]}^{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/980ebe9aa03e97113640dbb5403f7a02968ca0be)
- t-hashing：一个参数
，当某个编码 的任 
个元素必存在一个位置 ![{\displaystyle i\in [n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b389a8f1ad8a43d2bcf5194acf34e934f806311)
足以区别该 个元素，即是![{\displaystyle \forall u\in [t]j_{u}\in [M],\exists i\in [n]{\text{ st.}}x_{i}^{j_{u1}}\neq x_{i}^{j_{u2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b674547767039ce78ac8d0812c7e491ec1b1b9cd)
，此时称该编码是一个 t-杂凑函数。
- (m,q,k)-perfect hash family是一群杂凑函数H
(t,k)-hashing是一种k限问题。
杂凑函数![{\displaystyle h:[m]\rightarrow [q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca89b10e0969727616b088b228050794c5bc6594)
可以被视为是一个字串![{\displaystyle s\in [q]^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d553421f9cb929312d0d926ea5754e08af73eb4)
，![{\displaystyle h(x\in [m])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6a5a52633a5368d361dcdc5ad2077423bbecc37)
对应到![{\displaystyle s[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0341117200e6c837e1daba6db9c7cc24cdefd79d)
。
k个限制![{\displaystyle <math>f_{T,i\in [t]}\rightarrow \{0,1\},f(x)=1{\text{iff}}\forall i\in T\forall j\neq i\in [u],x[i]\neq x[j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d07a4f16c33d8fb42b784f5880550e6740e1c907)
，此处
。
Parent Identifying Code
[编辑 | 编辑源代码]定义如下：
- 一个(n,M)-code C的子集 X，给座标，有 n 个projection
就是每个x第 i位置的字元集合。
- X的envelope
