# Determine whether a variable has positive influence in Boolean function

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?

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

## 1 Answer

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$.

• 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})$. – rus9384 Sep 12 '17 at 19:01