如果 P 中的算法，提取解决方案的有效方法？
If algorithm in P, efficient way to extract solutions?
也许这很明显，但是如果我们在 P 中有一个算法（所以这个算法在多项式时间内给出 yes/no 答案），是否有比猜测和更有效的方法来找到解决方案正在检查？
因此，假设 SAT 在 P 中（我知道这是一个 NP 完全问题，但这似乎是我要问的问题的最佳示例）。这意味着有一个多项式时间算法会根据给定的输入是否可满足来告诉你是或否。
似乎应该有一种有效的方法来 find/extract 这个令人满意的任务（而不是仅仅知道它存在，如果有的话）。但是，我想不出任何有效的方法来利用这种多时间算法来找到这样的分配。
** 旁注 **
对于 maximization/minimization（例如背包）问题，我知道您可以使用二进制搜索来找到您的解决方案，但我的问题更多地与这些非最大化类型的问题有关，例如 SAT
您不必猜测整个事情然后再进行测试。
您可以获得满意的估值（如果存在），如下所示：
选择一个变量，将其设置为假，将其从所有 clauses/remove 满足条件的子句中删除。咨询 SAT oracle，它显然在今天以多项式时间运行。如果它仍然令人满意，那很好，保留它。否则一定为真，恢复子句，重新清理子句。没有回溯，每个变量只调用一次 SAT。整个事情仍然在多项式时间内。
或者，如果这就是您的想法，那么好吧，就是这样。这真的重要吗？多项式时间就是多项式时间，无论如何这在实践中是不可用的，所以挂钟时间几乎不是问题。
也许这很明显，但是如果我们在 P 中有一个算法（所以这个算法在多项式时间内给出 yes/no 答案），是否有比猜测和更有效的方法来找到解决方案正在检查？
因此，假设 SAT 在 P 中（我知道这是一个 NP 完全问题，但这似乎是我要问的问题的最佳示例）。这意味着有一个多项式时间算法会根据给定的输入是否可满足来告诉你是或否。
似乎应该有一种有效的方法来 find/extract 这个令人满意的任务（而不是仅仅知道它存在，如果有的话）。但是，我想不出任何有效的方法来利用这种多时间算法来找到这样的分配。
** 旁注 ** 对于 maximization/minimization（例如背包）问题，我知道您可以使用二进制搜索来找到您的解决方案，但我的问题更多地与这些非最大化类型的问题有关，例如 SAT
您不必猜测整个事情然后再进行测试。
您可以获得满意的估值（如果存在），如下所示：
选择一个变量，将其设置为假，将其从所有 clauses/remove 满足条件的子句中删除。咨询 SAT oracle，它显然在今天以多项式时间运行。如果它仍然令人满意，那很好，保留它。否则一定为真，恢复子句，重新清理子句。没有回溯，每个变量只调用一次 SAT。整个事情仍然在多项式时间内。
或者，如果这就是您的想法，那么好吧，就是这样。这真的重要吗？多项式时间就是多项式时间，无论如何这在实践中是不可用的，所以挂钟时间几乎不是问题。