2-SAT相關算法的多項式算法

我讀了很多找到2-SAT問題的算法，即給定的表達式是可滿足與否，可以用多項式時間求解。示例（algorithm）。
對於Krom的程序（Wikipedia），我構造了一個圖，從中我可以很容易地驗證它在多項式時間內的可滿足性。
現在，我想找到這個表達式的解決方案是可以滿足的。
我在想這個（驗證它）：首先我將任何形式的強連通分量表達式寫成x，並將值賦值爲0.然後按照算法，存在邊（x！ - > y）。因此y不能爲0.（因爲1 - > 0是錯誤的），並且如果可能的話，類似地繼續。
否則取x = 0，然後只有選擇y = 1，並且類似地繼續得到任何它可滿足的實例。2-SAT相關算法的多項式算法

現在，是在多項式時間內找到這個任何一個的任何可行的解決方案

提供一切可能的解決方案，其表現是令人滿意的。
或者這個表達式對於總共k個文字= 1的輸入是可滿足的。
或者表達式的最小數量有多少個值爲1可滿足。

我沒有得到這類問題的任何多項式算法。

來源

2015-11-04 piyush-balwani

提供一切可能的解決方案，其表現是令人滿意

沒有，因爲可以有許多成倍。

或者這表達是可滿足對於具有總共K文字輸入= 1

沒有，因爲如果這是容易的，那麼也將被加權2-滿足性（NP-硬）。

或者多少文字的最小數量的具有用於表達的值1是可滿足的

這是加權2-週六

來源

2015-11-04 22:54:09

Thanks @David。通過查看圖表，除了關於可滿足性的評論之外，還可以繪製哪些其他信息。 –

@ piyush-balwani這個問題太廣泛了，需要回答很有用。 –

2-SAT相關算法的多項式算法

回答

相關問題