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?

  • $\begingroup$ Doesn't this include SAT (the prototypical NP-complete problem) as a special case? $\endgroup$ – Federico Poloni Oct 12 '17 at 10:21
  • $\begingroup$ 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. $\endgroup$ – user1747134 Oct 12 '17 at 10:37
  • 1
    $\begingroup$ The problem “given $F$ (described by conjunctions of literals as in the question), is $\vec0\in F(\{0,1\}^n)$?” is exactly SAT. $\endgroup$ – Emil Jeřábek Oct 12 '17 at 10:59
  • $\begingroup$ 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. $\endgroup$ – user1747134 Oct 12 '17 at 11:48
  • 2
    $\begingroup$ $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. $\endgroup$ – Emil Jeřábek Oct 12 '17 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.