給定一有效可逼近的機率分布 
及其於某個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
