Tractable representations for Boolean functional synthesis

Given a Boolean relational specification F(X, Y), where X is a vector of inputs and Y is a vector of outputs, Boolean functional synthesis requires us to compute a vector of (Skolem) functions Psi(X), one for each output in Y, such that F(X, Psi(X)) <-> there exists Y F(X, Y) holds. This problem lies at the heart of many applications and has received significant attention in recent years. In this paper, we investigate the role of representation of F(X, Y) and of Psi(X) in determining the computational hardness of Boolean functional synthesis. We start by showing that an efficient way of existentially quantifying variables from a Boolean formula in a given order yields an efficient solution to Boolean functional synthesis and vice versa. We then propose a semantic normal form, called SynNNF, that guarantees polynomial-time synthesis and characterizes polynomial-time existential quantification for a given order of quantification of variables. We show that several syntactic and other semantic normal forms for Boolean formulas studied in the knowledge compilation literature are subsumed by SynNNF, and that SynNNF is exponentially more succinct than most of them. We also investigate how the representation of the synthesized (Skolem) functions Psi(X) affects the complexity of Boolean functional synthesis, and present a map of complexity based on the representations of F(X, Y) and Psi(X). Finally, we propose an algorithm to compile a specification represented as a NNF (including CNF) circuit to SynNNF. We present results of an extensive set of experiments conducted using an implementation of the above algorithm, and two other tools available in the public domain.