algorithm - 如果 P 中的算法，提取解决方案的有效方法？

Question

也许这很明显，但是如果我们在 P 中有一个算法(所以这个算法在多项式时间内给出是/否的答案)，是否有比猜测和检查更有效的方法来找到解决方案？

因此，假设 SAT 在 P 中(我知道这是一个 NP 完全问题，但这似乎是我要问的问题的最佳示例)。这意味着有一个多项式时间算法会根据给定的输入是否可满足来告诉您是或否。

因此似乎应该有一种有效的方法来查找/提取这个令人满意的分配(而不是仅仅知道它存在，如果有的话)。但是，我想不出任何有效的方法来利用这种多时间算法来找到这样的分配。

** 旁注 **对于最大化/最小化(例如背包)问题，我知道您可以使用二进制搜索来找到您的解决方案，但我的问题更多地与这些非最大化类型的问题有关，例如 SAT

Answer 1

您不必先猜测整个事情然后再进行测试。

您可以像这样获得令人满意的估值(如果存在):

选择一个变量，使其为假，将其从所有子句中删除/删除满意的子句。咨询 SAT oracle，它显然在今天以多项式时间运行。如果它仍然令人满意，那很好，保留它。否则一定为真，恢复子句，重新清理子句。没有回溯，每个变量只调用一次 SAT。整个过程仍在多项式时间内。

或者，如果这就是您的想法，那么好吧，就是这样。这真的重要吗？多项式时间就是多项式时间，无论如何这在实践中是不可用的，所以挂钟时间几乎不是问题。