使用 Z3 确定 BV 查询的量词消除难度

Question

我目前正在使用 Z3 C++ API 来解决对位向量的查询。某些查询可能在顶层包含存在量词。

通常情况下，量词消除很简单，Z3 可以快速完成。但是，在量词消除回退到枚举数千个可行解决方案的情况下，我想中止这种策略并以其他方式自己处理查询。

我尝试用 'try-for' 策略包装 'qe' 策略，希望如果量词消除失败（比如 100 毫秒），我知道我最好处理以其他方式查询。不幸的是，'try-for'-策略无法取消量词消除（对于任何时间限制）。

在 old post 中讨论了类似的问题，并且 'smt' 策略被指责为没有响应。同样的推理是否适用于 'qe' 策略？相同的 post 表示 'future' 版本应该更灵敏。 是否有任何方法或启发式方法来确定量词消除是否需要很长时间（除了运行求解器在单独的线程中并在超时时将其终止）？

我附上了一个最小的例子，所以你可以自己试试：

z3::context ctx;

z3::expr bv1 = ctx.bv_const("bv1", 10);
z3::expr bv2 = ctx.bv_const("bv2", 10);
z3::goal goal(ctx);
goal.add(z3::exists(bv1, bv1 != bv2));

z3::tactic t = z3::try_for(z3::tactic(ctx,"qe"), 100);    
auto res = t.apply(goal);
std::cout << res << std::endl;

谢谢！

Answer 1

必须通过运行策略定期检查超时取消。我们基本上必须确保代码检查取消并且不会在没有检查的情况下陷入长运行循环。您可能可以通过运行您的代码在调试器中识别未能检查取消的代码段，中断然后确定它在哪个过程中。然后在 GitHub 上提交错误以检查取消标志在有帮助的地方。总的来说，当涉及到位向量时，量词消除策略目前相当简单，因此除了简单的情况外，最好避免使用 qe。

使用 Z3 确定 BV 查询的量词消除难度

Use Z3 to determine difficulty of quantifier elimination for BV-queries

quantifiers

smt

z3