z3 behaviour changing on request for unsat core

Question

I have several SMTLIB2 examples which z3 normally finds unsat in 10s of milliseconds, yet, when I add in a request for it to generate unsat cores, the check-sat keeps going for minutes without returning. Is this behaviour to be expected? Does requesting unsat cores do more than just switch on instrumentation recording dependencies, and change which procedures and options z3 runs with? Is it possible to set further options so I see the same behaviour when I'm using unsat core generation as I see when I'm not using it?

I'm using Z3 4.3.1 (stable branch) on Scientific Linux 6.3.

The examples are in AUFNIRA, though several involve no reals and probably are not non-linear.

Thanks,

Paul.

Leonardo de Moura Leonardo de Moura · Accepted Answer · 2013-02-21T19:36:56

The unsat cores are tracked using "answer literals" (aka assumptions). When we enable unsat core extraction and use assertions such as

(assert  (! (= x 10) :named a1))

Z3 will internally create a fresh Boolean variable for the name a1, and assert

(assert  (=> a1 (= x 10)))

When, check-sat is invoked, it assumes all these auxiliary variables are true. That is, Z3 tries to show the problem is unsat/sat modulo these assumptions. For satisfiable instances, it will terminate as usual with a model. For unsatisfiable instances, it will terminate whenever it generates a lemma that contains only these assumed Boolean variables. The lemma is of the form (or (not a_i1) ... (not a_in)) where the a_i's are a subset of the assumed Boolean variables. As far as I know, this technique has been introduced by the MiniSAT solver. It is described here (Section 3). I really like it because it is simple to implement and we essentially get unsat core generation for free.

However, this approach has some disadvantages. First, some preprocessing steps are not applicable anymore. If we just assert

(assert (= x 10))

Z3 will replace x with 10 everywhere. We say Z3 is performing "value propagation". This preprocessing step is not applied if the assertion is of the form

(assert  (=> a1 (= x 10)))

This is just an example, many other preprocessing steps are affected. During solving time, some of the simplification steps are also disabled. If we inspect the Z3 source file smt_context.cpp we will find code such as:

   void context::simplify_clauses() {
        // Remark: when assumptions are used m_scope_lvl >= m_search_lvl > m_base_lvl. Therefore, no simplification is performed.
        if (m_scope_lvl > m_base_lvl)
            return;
        ...
   }

The condition m_scope_lvl > m_base_lvl) is always true when "answer literals"/assumptions are used. So, when we enable unsat core generation, we may really impact the performance. It seems that nothing is really for free :)

z3 behaviour changing on request for unsat core

1 Answers