1
$\begingroup$

Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$.
Given a function $f$ presented in $\text{CNF}$, and a coordinate, are there any known methods for determine if the coordinate has positive influence?

$\endgroup$
  • $\begingroup$ Finding all shortest implicates may deal with it. $\endgroup$ – rus9384 Sep 12 '17 at 12:01
  • 1
    $\begingroup$ A variable $x_i$ has zero influence if and only if the function doesn't depend on the variable. $\endgroup$ – Yuval Filmus Sep 12 '17 at 12:53
1
$\begingroup$

Given a CNF $\phi$ and a variable $x_i$, deciding whether $\phi$ depends on $x_i$ is NP-complete. It is clearly in NP: all we need to verify that $\phi$ depends on $x_i$ is two inputs different on $x_i$ on which $\phi$ evaluates to different values.

In the other direction, we reduce from SAT. Given a CNF $\psi = C_1 \land \cdots \land C_m$, let $x$ be a new variable and consider the CNF $\phi = \psi \land x$. If $\psi$ is satisfiable then $\phi$ depends on $x$, since substituting such a satisfying assignment reduces $\phi$ to $x$. If $\psi$ is not satisfiable then $\phi$ is always false, and in particular doesn't depend on $x$.

$\endgroup$
  • 1
    $\begingroup$ Well, this also gives a hint how to reduce it to SAT. Just make a formula $(\varphi\land x_i)\oplus(\varphi\land\overline{x_i})$. $\endgroup$ – rus9384 Sep 12 '17 at 19:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.