# How to compute image of boolean function

I have a function $F: \{0,1\}^n \to \{0,1\}^n$. Denote by $F_i : \{0,1\}^n \to \{0,1\}$ the $i$th component. I assume that for each $i$, $F_i$ can be written as conjunction of at most $n$ propositional literals (i.e. propositional variables or negated propositional variables). These formulas are known.

I am interested in obtaining the image $F(\{0,1\}^n)$ or it's complement from the syntax of the $F_i$ formulas, which I hope would be faster than enumerating the whole domain.

EDIT: Computing only $|F(\{0,1\}^n)|$ would be also useful to me.

Could anyone give me a hint how to approach such problem?

• Doesn't this include SAT (the prototypical NP-complete problem) as a special case? – Federico Poloni Oct 12 '17 at 10:21
• I was considering that, was unable to prove anything in this regard, but I thik not: The syntax here is very restricted, in contrast to SAT. – user1747134 Oct 12 '17 at 10:37
• The problem “given $F$ (described by conjunctions of literals as in the question), is $\vec0\in F(\{0,1\}^n)$?” is exactly SAT. – Emil Jeřábek Oct 12 '17 at 10:59
• But the inclusion goes other way than what @FedericoPoloni suggests, no? It can be solved as a SAT, yes,but SAT in general is not a special case of this. – user1747134 Oct 12 '17 at 11:48
• $F(\{0,1\}^n)=\{\vec1\}$ is trivially testable in polynomial time, as it is true only if every $F_i$ is defined as the empty conjunction. – Emil Jeřábek Oct 12 '17 at 12:37