Comment by gbacon

3 months ago

We care about Z3 because it is a Satisfiability Modulo Theories (SMT) solver.

Satisfiability: In 1971, Stephen A. Cook established that Boolean satisfiability, given an arbitrary Boolean formula whether an assignment to its variables exists that evaluates true, is NP-complete.

https://dl.acm.org/doi/10.1145/800157.805047

Translating between NP-complete problems is at most a polynomial (“fast”) amount of work, so every improvement gained on satisfiability (whose worst case is exponential rather than polynomial time complexity) benefits all other NP-complete problems, and thus the rest of NP.

Modulo Theories: We can think of SMT as a high-level language that automates encoding of other problems into raw Boolean formulas. Applications built on Z3 outsource search by encoding problems via one or more theories and then decoding results back to the problem domain at hand.

The benefits of doing this are (1) using an existing robust, well-tested suite of algorithms where (2) lots of research effort is concentrated and (3) improvements to Z3 improve your problem’s results more-or-less for free. According to Microsoft, “Z3 is used in a wide range of software engineering applications, ranging from program verification, compiler validation, testing, fuzzing using dynamic symbolic execution, model-based software development, network verification, and optimization.”

https://www.microsoft.com/en-us/research/project/z3-3/