本页使用了标题或全文手工转换

用户:TNTErick/k Restriction

来自维基学院
跳到导航 跳到搜索

本文主要探討關於k-限制問題(以下或簡稱k-限問題k-限)。並主要以Alon的論文[1]為參考對象。

主要內容(第二至五章)[编辑 | 编辑源代码]

定義集[编辑 | 编辑源代码]

符號及名詞解釋[编辑 | 编辑源代码]

  • [x]表示
  • 支集(英语:Support,記作)表示一個函數的定義域中所有使得

第一章[编辑 | 编辑源代码]

路徑問題[编辑 | 编辑源代码]

在有向圖中找是否有長度為k的路徑。

定義一: k-限制問題[编辑 | 编辑源代码]

k-限制問題由以下兩個敘述定義:

  1. 該問題的輸入為
    • 一個大小為 的字符集
    • 一個長度
    • 個函數 ,而每個函數不得為全否定函數,意即
  2. 該問題的輸出為一個集合 ,其中 的成員 滿足

由此可知,(即A的宇集)任何必將是任意k-限問題的一個解。但該解為最大解,即任何問題的窮舉。最理想是剔除掉所有不為解的 ,但k-限之難度是 NP,無法於多項式時間內得到該解集合,因此該論文以機率方法 限縮,而解集合的好壞取決於 的大小。即是,與集合中不為解的的個數有關。

第二章[编辑 | 编辑源代码]

定義二:機率密度[编辑 | 编辑源代码]

給定任意一個機率分布 ,一個k-限問題對於之中,的機率密度(之中抽到 的機率定義為

可見,每個和k-限問題相關的機率分布密度皆大於均勻分布的密度。而引用以下命題可以證明當一個機率分布中越大,越小。

命題一:併集限度[编辑 | 编辑源代码]

對於每個k-限及於其上的密度為 的分布,有一個至大為的解。

其證明利用反證法

設一個自然數 。考慮 ,其中 各不同,分別自中獨立取出。根據不等式 ,可得:

Moreover, picking slightly more vectors at random from D should yield a solution with high probability. But note that we do not know of an efficient way to verify a given set of vectors really does form a solution, unless k = Θ(1).

第三章[编辑 | 编辑源代码]

定義三:-笵距離 (p-笵線性距離)[编辑 | 编辑源代码]

直接建構出或許有些困難,但是我們可以建構出一個與其足夠接近的解。

在取樣空間中的兩個機率分布,他們的-笵距離定義為

k-限中爲,在其中有一機率分布,他的密度是,有一個在,若以後未特別定義則如此。

定義四:k-項,ε-相近[编辑 | 编辑源代码]

在取樣空間中的兩個機率分布,當 時,我們說二者在p-笵上的k-項是ε相近英语:k-wise ε-close in -norm

另外,一個分布當皆接近均勻分布則說他是k-項獨立

引理一[编辑 | 编辑源代码]

D,P是中,kε相近的兩個機率分布,根據定義,可得
證明:

展開拆開就結束啦

定義五:k-項逼近[编辑 | 编辑源代码]

引理二[编辑 | 编辑源代码]

命題二[编辑 | 编辑源代码]

第四章[编辑 | 编辑源代码]

定理一[编辑 | 编辑源代码]

證明見第五章。

定理二[编辑 | 编辑源代码]

引理三[编辑 | 编辑源代码]

應用一[编辑 | 编辑源代码]

命題三[编辑 | 编辑源代码]

引理四:貪婪[编辑 | 编辑源代码]

逼近分布[编辑 | 编辑源代码]

引理五:conacatenation[编辑 | 编辑源代码]

定理與其證明[编辑 | 编辑源代码]

本部分對應到原文的第五至第八章,將以其應用問題解決之。

第五章:項鍊分割[编辑 | 编辑源代码]

在此,我們會將k-限分作數個小部分並分別解決之。根據定理二可以找得到時的解,但是在此我們能夠找到... 接下來我們將運用項鍊分割來求解。

引理六:連續項鍊分割[编辑 | 编辑源代码]

Every interval t-coloring has a bsplitting of size (b − 1)t. Let us describe the intuition behind the case of t = b = 2, which provides some insight to the role of topology in the proof. Call one of the types red. Instead of observing some coloring of the unit interval, observe the equivalent coloring of the one-dimensional sphere (a necklace closed at its clasp). Consider some half necklace. If the measure of red within this half is exactly 1 2 , this induces a fair partition, and we are done. Otherwise, assume without loss of generality that this measure is larger than 1 2 . When rotating the necklace 180◦ , the measure of red in the observed half is hence smaller than 1 2 . As the change in the measure is continuous, there must be a half in which this measure is exactly 1 2 . In general, the proof uses a generalization of the Borsuk-Ulam theorem.

t pairwise disjoint subsets t個兩兩不相交的子集。

第六章:團體檢測[编辑 | 编辑源代码]

第七章:廣義雜湊[编辑 | 编辑源代码]

傳統上的完全雜湊 (m,q,k)-Perfect Hashing指的是將個元素雜湊至格的雜湊表的數個雜湊函數,其中必有至少一個雜湊函數對之中任k個的雜湊值皆不相同。

雜湊表
i= 1 2 3 ... m

這種雜湊其中的一個推廣是廣義雜湊 (t,u)-Hash Families#Alon2003中出現。

第八章:集合鋪蓋[编辑 | 编辑源代码]

參考文獻[编辑 | 编辑源代码]

  1. Alon, Noga; Moshkovitz, Dana; Safra, Shmuel. Algorithmic construction of sets for k -restrictions. ACM Transactions on Algorithms. 2006-04, 2 (2): 153–177. ISSN 1549-6325. doi:10.1145/1150334.1150336 (英语).