如何生成硬子集和實例
子集和問題可以定義為：
- 給定一組整數 $ S $
- 目標整數 $ x $
- 找到一些元素的子集 $ s \in S $ 這樣 $ \sum_0^{n}s_i = x $
子集和問題的“密度”定義為： $ \text{density} = \frac{k}{\operatorname{log}(\operatorname{max}(S))} $
在哪裡 $ k $ 是集合中的元素個數 $ S $ 和 $ \operatorname{log}(\operatorname{max}(S)) $ 是集合中最大元素的大小。
密度子集和問題 $ \lt 0.9408 $ 可以在多項式時間內求解。
我想知道：
我們如何生成無法在多項式時間內解決的子集和問題的硬實例，或者更具體地說，需要指數時間來解決？
- 使用任何尺寸集和元素是否足夠 $ \text{density} = 1 $ ? 假設所有集合元素都是均勻隨機且大小一致的 $ \operatorname{log}(\operatorname{max}(S)) $
- 更高的密度必然更困難嗎？
假設我們可以生成需要指數時間來解決的問題，那麼問題的指數參數是多少？
- 一套尺寸 $ 8 $ 和 $ 8 $ -位元素的密度為 $ 1 $ , 一組大小也是如此 $ 256 $ 和 $ 256 $ -bit 元素，所以如果 $ \text{density} = 1 $ 是對硬度的要求，那麼執行時間在密度參數中成指數是沒有意義的。
我們如何生成無法在多項式時間內解決的子集和問題的硬實例，或者更具體地說，需要指數時間來解決？
使用任何尺寸集和元素是否足夠 $ \text{density}=1 $ ? 假設所有集合元素都是均勻隨機且大小一致的 $ \operatorname{log}(\operatorname{max}(S)) $
假設我們可以生成需要指數時間來解決的問題，那麼問題的指數參數是多少？
條件和參數
最困難的例子有 $ \text{density} = 1 $ .
問題的一個例子 $ \text{density} = 1 $ 將需要時間指數的元素相加在一起。
要生成問題的硬實例，請確保：
集合中的元素個數 $ k $ 等於集合中最大元素的大小（以位為單位）
集合中的所有元素都大約是那個大小（你不能有一個大小的元素 $ \operatorname{log}(k) $ 其餘元素很小）。
每個實例應該總和（ $ k / 2) $ 集合的元素在一起。
- 如果你要總結 $ k - 1 $ 集合的元素在一起，那麼你可以解決一個更簡單的問題（即：從整個集合的總和中減去元素，直到你找到哪個（s）不是目標子集的成員）
成本
基本上，你需要 $ k $ 大小均勻隨機的元素 $ \operatorname{log}(k) $ 對於問題的一個硬實例。這意味著問題的硬實例將需要 $ O(k^2) $ 空間。
存在針對及時執行的子集和問題的量子攻擊 $ O((0.241… + O(1)) * n) $ , 我們將四捨五入 $ O(.25 * n) $ 使以下數學更方便：
假設使用上述條件的上述量子攻擊的複雜性，解決大小子集和問題的計算成本 $ k $ 是 $ O(2^{k / 8}) $ .
生成需要大約 $ O(2^{128}) $ 針對量子對手的計算成本，設置 $ k = 1024 $ .
- 這將使用 $ 1024^2 = 1048576 $ 位空間。
更高的密度必然更困難嗎？
不，問題的實例 $ \text{density} > 1 $ 更容易解決。