假設有一個可滿足性問題（稱為 oscillating-CNF），其中輸入是 CNF 子句的串列，我們想要證明這個問題確實是 NP 完全的（通過將 CNF-SAT 簡化為 oscillating-CNF）。當每個偶數索引子句 (0-2-4) 為真且每個非偶數索引子句為假 (1-3-5...) 時，一個令人滿意的振蕩 CNF 實體。
我的問題是，這是一個可行的策略：
- 從 CNF 中選擇一個隨機變數（稱為 R1）
- 否定 CNF 運算式
- 將步驟 2 中的否定運算式轉換回 CNF 格式
- 創建一個串列并在每個偶數索引位置 (R1 || !R1)，并在奇數索引中放置步驟 3 中的子句。
- 將此串列用作振蕩 CNF 問題的輸入
uj5u.com熱心網友回復：
問題是，當你否定一個析取從句時，它變成了一個連詞。我會將原始問題保留在偶數子句中，并為奇數子句引入輔助變數（在不包含原始變數的情況下使它們無法滿足）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409377.html
標籤：
上一篇：給定一個矩陣，如何在python中快速生成由其行元素組成的所有元組？[復制]
下一篇：使用Lambda的遞回快速排序