You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Incremental search never stops when the solver answers unknown at every depth #113
Since #103, an unknown answer is no longer read as UNSAT. When nothing is found, synthesis() raises SolverError. Without --max-depth, though, the incremental search has no upper bound. A solver that answers unknown at every depth therefore makes MILQ try depth after depth forever, and that error is never reached. #103's description already mentions this.
Minimal example. Here is a fake solver that answers unknown to every (check-sat):
cat > always-unknown <<'X'#!/bin/shwhile read -r line; do case "$line" in *check-sat*) echo unknown;; esacdoneX
chmod +x always-unknown
cat > solvers.toml <<'X'[solvers.unknown]path = "./always-unknown"logics = ["QF_LIA", "QF_NRA"]X
$ milq benchmarks/ghz/2.qasm -s smt -a unknown --solver-config solvers.toml -o out.qasm --max-depth 3
synthesis failed: 4 solver call(s) answered unknown: no circuit found, but none was proven not to exist
$ echo $?
1
A real solver hits this too: yices2 2.7.0 doesn't answer some Classic queries in reasonable time (#55's CI), and SMTInterpol answers unknown to nonlinear terms.
Possible fixes:
When the input is a circuit whose gates are all in the gate set, bound the search by the input's gate count, since the input itself is a solution at that depth.
Otherwise, stop after some number of consecutive depths that all answer unknown, or require --max-depth once an unknown has been seen.
Activity