为什么 MAX-SAT 是 SAT 问题的泛化？
Why is MAX-SAT a generalisation of the SAT problem?
根据维基百科，最大可满足性问题 (MAX-SAT) 是确定给定布尔公式的最大子句数的问题，该公式可以通过真值赋值实现到公式的变量。它是布尔可满足性问题的推广，它询问是否存在使所有子句为真的真值赋值。
我不明白第二句关于 MAX-SAT 是 SAT 的概括。根据维基百科，SAT 询问给定布尔公式的变量是否可以一致地替换为值 TRUE 或 FALSE，从而使公式的计算结果为 TRUE。
我问这个问题的原因是因为论文 'Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems'，我想在其中尝试半定优化技术来解决我手头的一些 SAT 问题。
想象一下，通过添加 p -> q，其中 p 是原始问题中每个子句 q 的新变量，将每个子句转化为含义。然后，当您选择那些求解器将 true 分配给相应的 p 的子句时，这个修改后的问题的一个令人满意的实例是原始 MAXSAT 问题的解决方案。这为您提供了一个 maxsat 求解器，尽管它很糟糕。
现在假设您有一个系统，可以确保尽可能多地使 p 为真。该组合现在为您提供了一个 maxsat 求解器，即可以优化 p 为真的数量的求解器。这样你就可以为你的原始问题得到一个很好的 maxsat 求解器，也就是说，你可以将 maxsat 问题减少到 sat，前提是你有一些东西可以最大化你通过翻译引入的 p 的真实分配数量.
@PatrickTrentin 可能会解释得更好！ vZ 论文（与 z3 关联的 maxsat 引擎）也是关于此主题的非常好且简单的读物：https://backend.orbit.dtu.dk/ws/portalfiles/portal/110977246/Bj_rner_Phan_Fleckenstein_Unknown_Z_An_Optimizing_SMT_Solver_1.pdf
根据维基百科，最大可满足性问题 (MAX-SAT) 是确定给定布尔公式的最大子句数的问题，该公式可以通过真值赋值实现到公式的变量。它是布尔可满足性问题的推广，它询问是否存在使所有子句为真的真值赋值。
我不明白第二句关于 MAX-SAT 是 SAT 的概括。根据维基百科，SAT 询问给定布尔公式的变量是否可以一致地替换为值 TRUE 或 FALSE，从而使公式的计算结果为 TRUE。
我问这个问题的原因是因为论文 'Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems'，我想在其中尝试半定优化技术来解决我手头的一些 SAT 问题。
想象一下，通过添加 p -> q，其中 p 是原始问题中每个子句 q 的新变量，将每个子句转化为含义。然后，当您选择那些求解器将 true 分配给相应的 p 的子句时，这个修改后的问题的一个令人满意的实例是原始 MAXSAT 问题的解决方案。这为您提供了一个 maxsat 求解器，尽管它很糟糕。
现在假设您有一个系统，可以确保尽可能多地使 p 为真。该组合现在为您提供了一个 maxsat 求解器，即可以优化 p 为真的数量的求解器。这样你就可以为你的原始问题得到一个很好的 maxsat 求解器，也就是说，你可以将 maxsat 问题减少到 sat，前提是你有一些东西可以最大化你通过翻译引入的 p 的真实分配数量.
@PatrickTrentin 可能会解释得更好！ vZ 论文（与 z3 关联的 maxsat 引擎）也是关于此主题的非常好且简单的读物：https://backend.orbit.dtu.dk/ws/portalfiles/portal/110977246/Bj_rner_Phan_Fleckenstein_Unknown_Z_An_Optimizing_SMT_Solver_1.pdf