为什么断言有效时 Z3 总是 return 未知？

Question

这是输入

示例 1

(declare-var a Int)
(declare-var b Int)
(declare-var n Int)
(assert (= b (* a a)))
(assert (not (= b (^ a 2))))
(check-sat)

示例 2

(declare-var a Int)
(declare-var b Int)
(declare-var n Int)
(assert (= b (* (^ a n) a)))
(assert (not (= b (^ a (+ n 1)))))
(check-sat)

它 returns 几乎瞬间未知。

Answer 1

你的问题属于不可判定的非线性整数运算片段。也就是说，没有决定程序来确定您的查询的可满足性。（非线性意味着，基本上，有一个涉及至少两个变量的乘法项。）

话虽如此，大多数求解器确实具有 启发式 来回答涉及非线性算术的查询，Z3 也不例外。当然，作为一种启发式方法，它可能会或可能不会产生答案。这就是您所观察到的，唉，Z3 使用的默认策略似乎不足以解决您的问题。

作为一个常用技巧，您可以尝试使用 Z3 的非线性实数算术求解器来解决这类问题。代替 check-sat，使用：

(check-sat-using qfnra-nlsat)

在这种情况下，Z3 假设输入是实数来尝试求解基准，并查看解是否实际上是整数。这个技巧可以成功地解决一些整数非线性算术查询，当然并非总是如此。例如，如果您在第一个示例中尝试 qfnra-nlsat，您会发现它成功解决了问题，但对于第二个示例，它仍然会回答 unknown。

有关非线性整数运算和 Z3 的详细信息，请参见此处：How does Z3 handle non-linear integer arithmetic?

Why Z3 always return unknown when assertions have power?