Как постоянные входные данные влияют на постановку задачи SAT?

Question

Допустим, у меня есть схема черного ящика с N входами и 1 выходом.

Я хочу зафиксировать значение M входов и найти значение остальных входов (NM), для которых схема является удовлетворительной. Если я вручную исправлю вводы M в RTL Verilog и преобразую его в CNF (используя abc), это даст правильный результат? Это правильный подход к такого рода проблемы?

Answer 1

Оригинальное пространство поиска вашей проблемы имеет 2^N записей. Фиксируя M входы, пространство поиска уменьшается в 2^M и имеет 2^(N-M) записей.

В зависимости от вашего выбора фиксированного M вводя значения, вы можете либо упростить поиск, либо слишком сильно сократить пространство поиска и в конечном итоге не найти решения.

Ваш черный ящик представляет собой комбинаторную схему, где выход зависит исключительно от текущего состояния входов? В RTL (регистрация уровня передачи / язык), вы также можете описать последовательный механизм, где выход также зависит от предыдущих входов.

Чтобы принять во внимание фиксированные входы, это называется Boolean Constraint Propagation. Это в основном упрощает вашу схему, так как могут быть удалены все элементы, которые имеют предопределенный выход. Примеры: Ан AND с одним или несколькими ложными входами имеет ложный выход. OR с одним или несколькими истинными входными данными есть истинные выходные и т. д. Другие упрощения включают удаление двойных отрицаний и инвертированных пар ввода XOR/XNOR ворота.

Вы могли бы взглянуть на bc2cnf, переводчик из булева формата списка цепей в файл DIMACS/CNF, перевариваемый SAT-решателем. Подобно ABC, bc2cnf будет распространять постоянные входные данные и доставлять довольно оптимизированный CNF.