如果算法在P中，提取解決方案的有效方式？

Question

也許這是非常明顯的，但是如果我們在P中有一個算法（所以這個算法在多項式時間中給出了是/否的答案），是否有更有效的方法來找到解決方案，而不僅僅是猜測和檢查？因此，假設SAT是在P（我知道這是一個NP完全問題，但這似乎是我想要問的最好例子）。這意味着存在一個多項式時間算法，根據給定的輸入是否可滿足會告訴您是或否。

似乎應該有一種有效的方式來找到/提取這個令人滿意的任務（而不是僅僅知道它存在，如果有的話）。然而，我想不出有什麼有效的方法來利用這種多時間算法來找到這樣的分配。

**側面說明** 對於最大化/最小化（例如揹包）問題，我知道，你可以使用二進制搜索找到你的解決方案，但我的問題是關於多像SAT

這些非最大化型問題

Answer 1

你不必猜測整個事物，然後測試它。

你可以得到一個滿意的估值（如果存在的話）是這樣的：

選擇一個變量，使假的，從所有條款刪除/刪除滿意的條款。 SAT諮詢，今天顯然運行在多項式時間。如果它仍然可以滿足，那就好了，保留它。否則，它必須是真的，恢復條款並再次清理條款。沒有回溯，每個變量只有一個SAT調用。整件事情仍處於多項式時間。或者如果這就是你的想法，那就好了，就是這樣。這真的很重要嗎？多項式時間是多項式時間，無論如何這在實踐中是不可用的，所以掛鐘時間幾乎不成問題。