On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms

We show ${\mathrm{\Sigma }}_2^p$-membership in the full version [29] and focus here on proving ${\mathrm{\Sigma }}_2^p$-hardness. Our proof is via reduction from succinct set cover, which is known to be ${\sum }_2^p$-complete [32, 31]. In the same way as for NP-hardness proofs, we need to give a polynomial time reduction to the decision problem variant of OfflineKnapExp such that the constructed instance is a YES-instance if and only if the given succinct set cover instance is a YES-instance.

We are given $n$ decision variables $x_1,\mathrm{\dots },x_n$, $m$ propositional logic formulas ${\varphi }_1,\mathrm{\dots },{\varphi }_m$ over these variables and an integer parameter $k$. Each formula ${\varphi }_j$ is in $3$-DNF form¹¹1Disjunctive normal form (DNF) refers to a disjunction of conjunctions, i.e., ${\varphi }_j=C_{j,1}\vee \mathrm{\dots }\vee C_{j,k_j}$, where each clause $C_{j,k}$ is a conjunction of literals. In 3-DNF, each $C_{j,k}$ contains exactly three literals. A formula in DNF is satisfied by a variable assignment if at least one clause is satisfied by the assignment. and we use $S_j$ to denote the set of $0$-$1$-vectors (variable assignments) that satisfy ${\varphi }_j$. The formulas ${\varphi }_j$ have to satisfy ${\bigcup }_{j\in \{1,\mathrm{\dots },m\}}{S}_j={\{0,1\}}^n$, i.e., each variable assignment satisfies at least one formula ${\varphi }_j$. The goal is to find a subset $S\subseteq \{1,\mathrm{\dots },m\}$ such that ${\bigcup }_{j\in S}{S}_j={\{0,1\}}^n$ and $|S|\le k$. We assume that each variable occurs as a literal in at least one formula. If not, we can just remove the variable and obtain a smaller instance. Succinct set cover can be interpreted as a set cover variant where the elements and sets are only given implicitly and not as an explicit part of the input.

Before we give the technical details of the reduction, we first sketch the basic idea. In particular, we describe the properties that we want the constructed instance to have. In the technical part, we then describe how to actually achieve these properties. At its core, the reduction will use the knapsack weights to encode structural information of the input instance into the constructed instance. The idea to use numerical weights to encode constraints is quite natural in hardness proofs for weakly NP-hard problems, see e.g. the NP-hardness proof for the subset sum problem given in [22]. The usage of the knapsack weights in our reduction is on some level inspired by such classical reductions, but requires several new ideas to handle the implicit representation of the input problem and the covering nature of OfflineKnapExp.

First, we introduce a single trivial item $i^{\ast }$ with $w_{i^{\ast }}=p_{i^{\ast }}=B$. This item alone fills up the complete knapsack capacity $B$, which we define later, and the instance will be constructed in such a way that $p^{\ast }=p_{i^{\ast }}=B$ is the maximum profit of any packing. Thus, only packings $P$ with $U_P>p^{\ast }$ induce non-trivial constraints in (K-ILP). We design the instance such that $U_P\ge p^{\ast }$ only holds for packings that use the full capacity.

Next, we want each packing $P$ with $w(P)=B$ and $U_P>p^{\ast }$ to represent a distinct variable assignment in ${\{0,1\}}^n$. To this end, we introduce a set $X$ of $2n$ items, two items $v_i$ and ${\overline{v}}_i$ for each variable $x_i$ with $i\in \{1,\mathrm{\dots },n\}$. Intuitively, $v_i$ represents the positive literal $x_i$ and ${\overline{v}}_i$ represents the negative literal $\neg x_i$. We say that a subset $X^{\prime }\subseteq X$ represents a variable assignment if $|X^{\prime }\cap \{v_i,{\overline{v}}_i\}|=1$ for all $i\in \{1,\mathrm{\dots },n\}$. We design our instance such that the packings $P$ with $w(P)=B$ and $U_P>p^{\ast }$ exactly correspond to the variable assignments in ${\{0,1\}}^n$. Note that this excludes the packing $P=\{i^{\ast }\}$ as this packing has $w(P)=B$ and $p(P)=p^{\ast }$.

If the first two properties hold, then all non-trivial constraints in the ILP (K-ILP) for the constructed instance correspond to a packing $P$ with $w(P)=B$ and $U_P>p^{\ast }$ and, thus, to a variable assignment of the given succinct set cover instance. Furthermore, each variable assignment is represented by at least one active constraint. With the next property, we want to ensure that each possible query, i.e., each non-trivial item, corresponds to a succinct set cover formula ${\varphi }_j$. To this end, we introduce the set of items $Y=\{y_1,\mathrm{\dots },y_m\}$. These items will be the only non-trivial items in the constructed instance, so each possible query is to an element of $Y$. Next, we want to achieve that querying an item $y_j$ suffices to satisfy all constraints of (K-ILP) for packings $P$ with $w(P)=B$ and $U_P>p^{\ast }$ that represent a variable assignment which satisfies formula ${\varphi }_j$, and does not impact any other constraints. Formally, we would like to design our instance such that the following property holds.

If we manage to define our reduction in such a way that the three properties are satisfied, it is not hard to show correctness (see the full version [29] for the second direction):

If there is an index set $S$ with $|S|\le k$ that is a feasible solution to the succinct set cover instance, then each possible variable assignment must satisfy at least one formula ${\varphi }_j$ with $j\in S$. We claim that $Q=\{y_j\mid j\in S\}$ is a feasible query set for the constructed OfflineKnapExp instance. To this end, consider an arbitrary packing $P$ with $U_P>p^{\ast }$, which are the only packings that induce non-trivial constraints in the corresponding (K-ILP). By Property 1, we have $w(P)=B$. Property 2 implies that $X\cap P$ represents some variable assignment $\phi$ and Property 3 implies that $y_j\in P$ for all ${\varphi }_j$ that are satisfied by $\phi$. By assumption that $S$ is a feasible succinct set cover solution, we get $Q\cap P\ne \mathrm{\varnothing }$. Property 3 implies $U_P(Q)\le U_P(\{y_j\})\le p^{\ast }$ for each $y_j\in Q\cap P$. Thus, $Q$ satisfies the constraint of $P$ in the (K-ILP) for the constructed instance. As this holds for all $P$ with $U_P>p^{\ast }$, the set $Q$ is a feasible solution for the constructed OfflineKnapExp instance.

It remains to show how to actually construct an OfflineKnapExp instance that satisfies the three properties. Given an instance of succinct set cover, we construct an instance of OfflineKnapExp consisting of four sets $X,\mathrm{\Phi }$, $A$ and $L$ of items such that $ℐ=X\cup \mathrm{\Phi }\cup A\cup L$. The set $X$ is defined exactly as sketched above, the set $\mathrm{\Phi }$ contains the set $Y=\{y_j,\mathrm{\dots },y_m\}$ as introduced above, and $L:=\{i^{\ast }\}$ for the item $i^{\ast }$ with $w_{i^{\ast }}=p_{i^{\ast }}=B$. All further items will be used to ensure the three properties.

Conceptionally, we construct several partial weights for each item $i$ that will later be combined into a single weight. For each item $i$, we construct two weights $w_{i,{\varphi }_j}$ and $w_{i,{\rho }_j}$ for each formula ${\varphi }_j$, and a single weight $w_{i,x}$. Similarly, we break down the knapsack capacity into multiple partial knapsack capacities $B_x$, and $B_{{\varphi }_j},B_{{\rho }_j}$ for each ${\varphi }_j$. Intuitively, the full weight $w_i$ of an item $i$ will be the concatenation of the decimal representations of the partial weights, i.e., $w_i=w_{i,x}{w}_{i,{\rho }_m}\mathrm{\cdots }{w}_{i,{\rho }_1}{w}_{i,{\varphi }_m}\mathrm{\cdots }{w}_{i,{\varphi }_1}$, and $B$ will be the concatenation of the partial capacities. We make this more precise in the full version [29] after defining all partial weights in such a way that the following property holds.

For now, we operate under the assumption that Property 4 holds and focus on the partial weights and capacities, and proceed by defining the remaining parts of the construction.

As formulated in Property 2, we would like each packing $P$ with $w(P)=B$ and $U_P>p^{\ast }$ to represent a variable assignment. To this end, we need such a packing to contain exactly one item of $\{v_i,{\overline{v}}_i\}$ for each $i\in \{1,\mathrm{\dots },n\}$. To enforce this, we use the partial $w_x$-weights and the partial capacity $B_x$. In particular, we define $w_{v_i,x}=w_{{\overline{v}}_i,x}={10}^i$ for each $i\in \{1,\mathrm{\dots },n\}$, and $B_x={\sum }_{i=1}^n{10}^i$. For all items $j\in ℐ\setminus X$, we define $w_{j,x}=0$, which immediately implies the following property:

Define $A={\bigcup }_{j\in \{1,\mathrm{\dots },m\}}{A}_{{\varphi }_j}$ for sets $A_{{\varphi }_j}$ to be defined below. For formula ${\varphi }_j$, let $k_j$ denote the number of clauses in ${\varphi }_j$ and let $C_{j,1},\mathrm{\dots },C_{j,k_j}$ denote these clauses. For each $C_{j,k}$, we add four items $a_{j,k,0},a_{j,k,1},a_{j,k,2},a_{j,k,3}$ to set $A_{{\varphi }_j}$. The idea is to define the partial $w_{{\varphi }_j}$-weights and the partial $B_{{\varphi }_j}$ capacity in such a way that the following property holds.

To achieve the property, we first define the partial $w_{{\varphi }_j}$-weights for the items $X$. For a literal $x_i$, let ${𝒞}_{x_i,j}:=\{k\mid x_i\text{ occurs in }{C}_{j,k}\}$ and define ${𝒞}_{\neg x_i,j}$ in the same way. We define the weights $w_{v_i,{\varphi }_j}$ and $w_{{\overline{v}}_i,{\varphi }_j}$ as ${\sum }_{k\in {𝒞}_{x_i,j}}{10}^{k_j+k-1}$ and ${\sum }_{k\in {𝒞}_{\neg x_i,j}}{10}^{k_j+k-1}$, respectively. Intuitively, digit $k_j+k$ of the sum ${\sum }_{h\in X\cap P}{w}_{h,{\varphi }_j}$ of a packing $P$ with ${\sum }_{i\in P}{w}_{i,x}=B_x$ indicates whether the assignment represented by $X\cap P$ satisfies clause $C_{j,k}$ or not: If the clause is satisfied, then $X\cap P$ contains the items that represent the three literals of $C_{j,k}$ and the digit has value $3$. Otherwise, $X\cap P$ contains at most two of the items that represent the literals of $C_{j,k}$ and the digit has value at most $2$.

Finally, for each for $i\in \{0,1,2,3\}$, we define the $w_{{\varphi }_j}$-weight of item $a_{j,k,i}$ as $w_{{\varphi }_j,a_{j,k,i}}=i\cdot {10}^{k_j+k-1}+{10}^{k-1}$. For all remaining items $i\in ℐ\setminus (X\cup A_{{\varphi }_j})$, we define the partial $w_{{\varphi }_j}$-weight to be zero. Furthermore, we define the partial capacity $B_{{\varphi }_j}={\sum }_{k=0}^{k_j-1}{10}^k+{\sum }_{k=k_j}^{2k_j-1}3\cdot {10}^k$. We claim that these definitions enforce Property 6.

Intuitively, the fact that the $k_j$ decimal digits of lowest magnitude in $B_{{\varphi }_j}$ have value $1$ forces a packing $P$ with ${\sum }_{i\in P}{w}_{i,{\varphi }_j}=B_{{\varphi }_j}$ to contain exactly one item of $\{a_{j,k,0},\mathrm{\dots },a_{j,k,3}\}$ for each $k\in \{1,\mathrm{\dots },k_j\}$ as each such item increases the corresponding digit $k-1$ by one. Similarly, the value of each digit $k_j+k-1$ in $B_{{\varphi }_j}$ is three. Since the elements of $X$ that occur in clause $C_{j,k}$ increase the value of digit $k_j+k-1$ in $w_{{\varphi }_j}(P)$ by one and item $a_{j,k,i}$ increases the digit by $i$, a packing $P$ with value three in digit $k_j+k-1$ of $w_{{\varphi }_j}(P)$ can contain item $a_{j,k,0}$ if and only if $X\cap P$ contains the three items that correspond to the literals in $C_{j,k}$. This implies Property 6. We give a more formal argumentation in the full version [29].

Define $\mathrm{\Phi }={\bigcup }_{j\in \{1,\mathrm{\dots },m\}}{\mathrm{\Phi }}_j$ such that ${\mathrm{\Phi }}_j=\{y_j,u_j,f_{j,0},\mathrm{\dots },f_{j,k_j-1}\}$. Note that $y_j$ is the item that has already been introduced for Property 3. As a step toward enforcing this property, we define the $w_{{\rho }_j}$-weights such that:

To enforce this property, we define the following partial capacity $B_{{\rho }_j}=k_j+{10}^{k_j^2}+{10}^{k_j^2+1}$. Next, we define the $w_{{\rho }_j}$-weight of the elements $a_{j,k,0}$, $k\in \{1,\mathrm{\dots },k_j\}$, as $w_{a_{j,k,0},{\rho }_j}=1$. Furthermore, we define $w_{u_j,{\rho }_j}={10}^{k_j^2+1}+{10}^{k_j^2}+k_j$, $w_{y_j,{\rho }_j}={10}^{k_j^2+1}$ and $w_{f_{j,k},{\rho }_j}={10}^{k_j^2}+k$, for all $k\in \{0,\mathrm{\dots },k_j-1\}$. For all other items, define the $w_{{\rho }_j}$-weight to be zero. We show in the full version [29] that these definitions imply Property 7.

To finish the reduction, we define the profits and uncertainty intervals of all introduced items:

• $\mathrm{■}$

  For the items $y_j$, $j\in \{1,\mathrm{\dots },m\}$, we define the uncertainty interval $I_{y_j}=(w_{y_j}-2,w_{y_j}+ϵ)$ for a fixed . We define the profits as $p_{y_j}=w_{y_j}-1$.

• $\mathrm{■}$

  For all items $i\in ℐ\setminus \{y_j\mid j\in \{1,\mathrm{\dots },m\}\}$, we use trivial uncertainty intervals $I_i=\{w_i\}$.

With the full construction in place, we are ready to prove the three main properties from the beginning of the proof:

1. 1.

   Property 1: By definition of the profits, we have $p(P)\le w(P)$ for each packing $P$, which implies that the maximum profit is $p^{\ast }\le B$. Since the packing $P=L=\{i^{\ast }\}$ has a profit of exactly $B$, we get $p^{\ast }=B$. On the other hand, the upper limit $U_P$ of a packing $P$ is $w(P)+ϵ|P\cap \{y_j\mid j\in \{1,\mathrm{\dots },m\}\}|$ as only the items in $\{y_j\mid j\in \{1,\mathrm{\dots },m\}\}$ have a non-trivial uncertainty interval with upper limits of $w_{y_j}+ϵ$. By choice of $ϵ$, this gives . Since all weights are integer, this implies that $U_P\ge p^{\ast }=B$ only holds if $w(P)=B$.

2. 2.

   Property 2: The property, in particular the first part, is essentially implied by Property 4 and Property 5. We give the formal argumentation in the full version [29].

3. 3.

   Property 3: By Property 1 and definition of the uncertainty intervals, a packing $P$ has $U_P>p^{\ast }$ if and only if $w(P)=B$ and $P\ne \{i^{\ast }\}$. By Property 4, the latter holds if and only if $w_x(P)=B_x$, $w_{{\varphi }_j}(P)=B_{{\varphi }_j}$ and $w_{{\rho }_j}(P)=B_{{\rho }_j}$ for all $j\in \{1,\mathrm{\dots },m\}$. Fix a packing $P$ with $y_j\in P$ for some $j\in \{1,\mathrm{\dots },m\}$. By Property 7, $y_j\in P$ holds if and only if $a_{j,k,0}\in P$ for some clause $C_{j,k}$ in ${\varphi }_j$. By Property 6, $a_{j,k,0}\in P$ if and only if $C_{j,k}$ is satisfied by the assignment represented by $X\cap P$. This gives the first part of Property 3. For the final part, observe that $U_{y_j}-p_{y_j}>1$. On the other hand, . Hence, the second part of Property 3 holds.

To finish the proof of the reduction, it remains to argue about the running time and space complexity of the reduction. We do so in the full version [29]. The main argument is that, while the numerical values of the constructed weights are exponential, the number of digits in their decimal representations (and, thus, their encoding size) is polynomial. $◀$

The previous theorem proves ${\sum }_2^p$-hardness for OfflineKnapExp. Exploiting the inapproximability result on the succinct set cover problem given in [30, Theorem 7.2], we can show the following stronger statement by using the same reduction (cf. the full version [29] for a formal proof).