z3py: Как правильно утверждать, что ограничение чего-то не существует?

Я хочу установить ограничение «что-то не должно существовать» в z3py. Я попытался использовать «Не (существует (...))». Простой пример таков. Я хочу найти задание для a и b, чтобы такого c не существовало.

from z3 import *

s = Solver()
a = Int('a')
b = Int('b')
c = Int('c')

s.add(a+b==5)
s.add(Not(Exists(c,And(c>0,c<5,a*b+c==10))))
print s.check()
print s.model()

Выход

sat
[b = 5, a = 0]

Что кажется правильным. Но когда я пишу ограничение «Не (существует (...))» в более сложной задаче, это может занять несколько часов без создания решения. Интересно, является ли это правильным и наиболее эффективным способом утверждения ограничения «не существует»? Или такие задачи с кванторами трудно решить любым решателем?


exists z3 smt z3py quantifiers
person Zhongjun 'Mark' Jin    schedule 12.07.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

То, как вы написали это ограничение, просто прекрасно. И неудивительно, что Z3 (или любой другой решатель) будет тяжело решать такие задачи, ведь у вас есть и квантификаторы, и нелинейная арифметика. Такие проблемы внутренне трудно решить.

Вы можете изучить тактику Z3 nlsat, которая может принести некоторое облегчение здесь: 13898524">Как Z3 обрабатывает нелинейную целочисленную арифметику?

Или вы можете попробовать reals вместо целых чисел или битовых векторов (т.е. машинных целых чисел). Конечно, сможете ли вы на самом деле использовать эти типы, будет зависеть от вашей проблемной области. (Вещественные числа, очевидно, будут иметь «дробные» значения, а битовые векторы подчиняются модульной арифметике.)

person alias    schedule 14.07.2015
comment
Спасибо, Левент. Это действительно полезно. - person Zhongjun 'Mark' Jin; 14.07.2015