前導

編輯

定理一

編輯

給定一有效可逼近的機率分布   及其於某個k-限   上的密度  ,並給出一個instance 以及精度參數  可以得到一個不大於 的解 ,且時間複雜度是 的多項式函數。

(第四章)

與asym. optimal errCrct. code的關係

編輯

Alon1992 中指出的

定義

編輯
  •   是一個具字母數為  的鍵集。
  • 任何子集 皆被視為(n,M)-code (n 碼長、M項的編碼)。
  • code rate 編碼效率定義為  
  • 一個編碼  codeword 字串  ( 中每一個 的元素),其中第 i 個字母表示作 
  • t-hashing:一個參數 ,當某個編碼   的任   個元素必存在一個位置   足以區別該   個元素,即是 ,此時稱該編碼是一個 t-雜湊函數。
  • (m,q,k)-perfect hash family是一群雜湊函數H

與 k限之間之關係

編輯
(t,k)-hashing是一種k限問題。

雜湊函數 可以被視為是一個字串  對應到 。 k個限制 ,此處 

Parent Identifying Code

編輯

定義如下:

  1. 一個(n,M)-code C的子集 X,給座標 ,有 n 個projection  就是每個x第 i位置的字元集合。
  2. X的envelope