<p>As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for graphs succinctly defined using CNF formulas to the problem that I have described. The dominant set problem is known to be NExpTime complete [1] for graph succinctly defined using CNF formulas.</p>
<p>An instance of DominantSet^{2^n}<em>{CNF} is defined by an CNF formula E(X,Y) over X={x_1,x_2,…,x_n} and Y={y1,y2,…,y_n}, two sets of n Boolean variables, and an integer K (encoded in binary) . The formula E(X,Y) succinctly defines the following graph: the set of vertices is the set of all Boolean valuations over n variables: 2^n, so any valuation v for the set of variables X, or for the set of variables Y, defines a vertex. Let v_1 and v_2 be two such valuations, then there is an edge={v_1,v_2} in the graph iff E(v_1,v_2) is true or E(v_2,v_1) is true.  An instance is positive, if there exists a set of K valuations V={v_1,v_2,…,v_K} such that \cup</em>{v \in V} { v’ | E(v,v’) \lor E(v’,v) }=2^n (i.e. all vertices are adjacent to a vertex in V).</p>
<p>We can reduce in polynomial time this problem to our succinct set cover problem as follows:</p>
<p>Define (U) to be the empty CNF formula over the set of n variables U (which is equivalent to true) and so [A(U)]=2^n. Then define B(Z,U) to be the CNF equivalent to E(Z,U) \lor E(U,Z). This last formula has a size which is polynomial in the size of the CNF E that defines the graph. Keep K unchanged.</p>
<p>Then it is direct to see that the instance of succinct set cover is positive iff the DominantSet instance is positive. Indeed, there is a set V of K valuations for the variables in Z such that \bigcup_{v \in V} { v' | B(v,v') } covers 2^n iff V is a dominant set.</p>
<p>[1] Patrick Schafenacker. Problems on succinctly encoded graphs. PhD dissertation. Universität Ulm 2017.</p>

CC BY-SA 4.0
2020-12-17T13:30:35.053Z
2020-12-17T13:30:35.053Z
Jean-Francois Raskin
<p>Notation: given a CNF formula A over variables X, we write <span class="math-container">$[A(X)]$</span> for the set of valuations <span class="math-container">$v: X \to \{0,1\}$</span> such that <span class="math-container">$A(X/v)$</span> is true, i.e. the set of valuations that makes formula A true.</p>
<p>I suspect that the following problem is NExpTime-complete:</p>
<p>-given two CNF formulas <span class="math-container">$A(X)$</span> and <span class="math-container">$B(Y,X)$</span>, and an integer <span class="math-container">$K=2^k$</span>, determine if there exist <span class="math-container">$K$</span> valuations <span class="math-container">$v_1,v_2,...,v_K : Y \to {0,1}$</span> such that <span class="math-container">$[A(X)] \subseteq \bigcup_{v=v_1,v_2,...,v_K} [B(Y/v,X)]$</span>, i.e. are there K valuations of the variables in Y such that all the valuations that makes <span class="math-container">$A(X)$</span> true are covered by valuations that makes <span class="math-container">$B(Y/v,X)$</span> true.</p>
<p>So this can be seen as a succinct encoding of the set cover problem using CNF formulas. My guess is that this result should be a consequence of the NP completness of set cover and some general results about succinct encodings of problems using CNF formulas. Unfortunately, I was not able to locate such a result in the literature...</p>

<complexity><set-cover><nexp><succinct>
CNF encoding of set cover - NExpTime-completness
Jean-Francois Raskin
# CNF encoding of set cover - NExpTime-completness

(Asked by: username_0 on 2020-12-07)

Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true.

I suspect that the following problem is NExpTime-complete:

-given two CNF formulas $A(X)$ and $B(Y,X)$, and an integer $K=2^k$, determine if there exist $K$ valuations $v\_1,v\_2,...,v\_K : Y \to {0,1}$ such that $[A(X)] \subseteq \bigcup\_{v=v\_1,v\_2,...,v\_K} [B(Y/v,X)]$, i.e. are there K valuations of the variables in Y such that all the valuations that makes $A(X)$ true are covered by valuations that makes $B(Y/v,X)$ true.

So this can be seen as a succinct encoding of the set cover problem using CNF formulas. My guess is that this result should be a consequence of the NP completness of set cover and some general results about succinct encodings of problems using CNF formulas. Unfortunately, I was not able to locate such a result in the literature...

**Tags:** complexity, set-cover, nexp, succinct

---

## 1 answers

### Answer by username_0 on 2020-12-17. Score: 1

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for graphs succinctly defined using CNF formulas to the problem that I have described. The dominant set problem is known to be NExpTime complete [1] for graph succinctly defined using CNF formulas.

An instance of DominantSet^{2^n}*{CNF} is defined by an CNF formula E(X,Y) over X={x\_1,x\_2,…,x\_n} and Y={y1,y2,…,y\_n}, two sets of n Boolean variables, and an integer K (encoded in binary) . The formula E(X,Y) succinctly defines the following graph: the set of vertices is the set of all Boolean valuations over n variables: 2^n, so any valuation v for the set of variables X, or for the set of variables Y, defines a vertex. Let v\_1 and v\_2 be two such valuations, then there is an edge={v\_1,v\_2} in the graph iff E(v\_1,v\_2) is true or E(v\_2,v\_1) is true. An instance is positive, if there exists a set of K valuations V={v\_1,v\_2,…,v\_K} such that \cup*{v \in V} { v’ | E(v,v’) \lor E(v’,v) }=2^n (i.e. all vertices are adjacent to a vertex in V).

We can reduce in polynomial time this problem to our succinct set cover problem as follows:

Define (U) to be the empty CNF formula over the set of n variables U (which is equivalent to true) and so [A(U)]=2^n. Then define B(Z,U) to be the CNF equivalent to E(Z,U) \lor E(U,Z). This last formula has a size which is polynomial in the size of the CNF E that defines the graph. Keep K unchanged.

Then it is direct to see that the instance of succinct set cover is positive iff the DominantSet instance is positive. Indeed, there is a set V of K valuations for the variables in Z such that \bigcup\_{v \in V} { v' | B(v,v') } covers 2^n iff V is a dominant set.

[1] Patrick Schafenacker. Problems on succinctly encoded graphs. PhD dissertation. Universität Ulm 2017.


---

