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