A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing

Jansen, Klaus; Ohnesorge, Felix; Pirotton, Lis

doi:10.4230/LIPIcs.ICALP.2026.116

A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing

Klaus Jansen

Kiel University, Germany Felix Ohnesorge

Kiel University, Germany Lis Pirotton

Kiel University, Germany

Abstract

Consider a high-multiplicity Bin Packing instance $I$ with $d$ distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime ${{|I|}^{2}}^{O(d)}$ for this problem [SODA’14], where $|I|$ denotes the encoding length of the instance $I$ . Although Jansen and Klein [SODA’17] later developed an algorithm that improves upon this runtime in a special case, it has remained a major open problem by Goemans and Rothvoss [J.ACM’20] whether the doubly exponential dependency on $d$ is necessary.

We solve this open problem by showing that unless the Exponential Time Hypothesis (ETH) fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time ${{|I|}^{2}}^{o(d)}$ . To prove this, we introduce a novel reduction from 3-SAT. The core of our construction is efficiently encoding all information from a 3-SAT instance with $n$ variables into an ILP with $O(\log n)$ variables and constraints.

This result confirms that the Goemans and Rothvoss algorithm is essentially best-possible for Bin Packing parameterized by the number $d$ of item sizes in the context of XP time algorithms.

Keywords and phrases:

Bin Packing, Lower Bound, Computational Complexity, ETH

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Fixed parameter tractability

Related Version:

Full Version: https://arxiv.org/abs/2512.02691

Acknowledgements:

We thank Alberto Del Pia and Timo Berthold for discussions on constraint linearization and Stefan Weltge for pointing us to the references [24, 35]. The idea for this work originated during a visit of Klaus Jansen to the MPI – INF Saarbrücken in 2024.

Funding:

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project number 453769249.

DOI:

10.4230/LIPIcs.ICALP.2026.116

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Bin Packing problem is a classic optimization problem with many applications.

Definition 1 (Bin Packing).

Given are $d\in\mathbb{Z}_{>0}$ item types with sizes $\boldsymbol{s}=(s_{1},\ldots,s_{d})\in(0,B]^{d}$ and multiplicities $\boldsymbol{a}=(a_{1},\ldots,a_{d})\in\mathbb{Z}_{>0}^{d}$ . The Bin Packing problem asks to find the minimum number of bins of size $B\in\mathbb{Z}_{>0}$ to pack all items.

The Bin Packing problem is also known as the (1-dimensional) Cutting Stock problem, and its study goes back to the classical paper by Gilmore and Gomory [9]. While the problem is strongly NP-hard in general, a major research direction has focused on parameterized algorithms for the high-multiplicity setting, where $d$ is assumed to be a small parameter. A breakthrough result in this area came in 2014 from Goemans and Rothvoss [11], who proved that it is solvable in polynomial time for constant $d$ . This answered an open question posed by McCormick, Smallwood and Spieksma [33], as well as by Eisenbrand and Shmonin [6].

To obtain their result, Goemans and Rothvoss [11] study the more general Cone and Polytope Intersection problem, defined as follows: Given two polytopes $\mathcal{P},\mathcal{Q}\subseteq\mathbb{R}^{d}$ : Is there a point in $\mathcal{Q}$ that can be expressed as a non-negative integer combination of integer points in $\mathcal{P}$ ? They gave an algorithm for this feasibility problem with time complexity ${{|\mathcal{P}|}^{2}}^{O(d)}\cdot|\mathcal{Q}|^{O(1)}$ , where $|\mathcal{R}|$ denotes the encoding length of a polytope $\mathcal{R}\in\{\mathcal{P},\mathcal{Q}\}$ . Additionally, they show how to construct a Cone and Polytope Intersection instance from any Bin Packing instance. In this transformation, $\mathcal{P}=\{\binom{\boldsymbol{x}}{1}\in\mathbb{R}^{d+1}_{\geq 0}\mid% \boldsymbol{s}^{\intercal}\boldsymbol{x}\leq B\}$ (the knapsack polytope) contains all possible configurations $\boldsymbol{x}$ (i.e., multiplicity vectors of items that fit into a single bin), and $\mathcal{Q}=\{\boldsymbol{a}\}\times[0,k]$ is constructed to encode the target item vector $\boldsymbol{a}$ and the number of bins $k$ . Using binary search over $k$ , this yields an algorithm for Bin Packing with runtime ${{|I|}^{2}}^{O(d)}$ , where $|I|$ denotes the encoding length of the instance. For $d=O(1)$ the encoding length is $|I|=O(\log(\Delta))$ , where $\Delta=\max\{\|\boldsymbol{a}\|_{\infty},\|\boldsymbol{s}\|_{\infty},B\}$ .

This result was later improved by Jansen and Klein [17]. They gave an algorithm with time complexity ${{|V|}^{2}}^{O(d)}\cdot\log(\Delta)^{O(1)}$ , where $V$ is the set of vertices of the corresponding integer knapsack polytope. This result improves upon the algorithm in [11] if the number of vertices $|V|$ is small. Since $|V|\geq d+1$ , this gives a Fixed-Parameter Tractable (FPT) algorithm parameterized by the number of vertices in the integer knapsack polytope. On the other hand, the number of vertices can be bounded only by $|V|=O(\log\Delta)^{2^{O(d)}}$ [3, 12]. Therefore, the algorithm by Jansen and Klein has a worst case running time $O(\log\Delta)^{2^{O(d)}}$ which is identical to the running time of the algorithm by Goemans and Rothvoss.

Goemans and Rothvoss [11] wrote in their journal paper:

“A natural open problem that arises from this work is whether the double exponential running time is necessary.”

In addition to this question, they asked whether Bin Packing can be solved in FPT time $f(d)\cdot O(\log(\Delta))^{O(1)}$ , where $f(d)$ is an arbitrary function.

Recent work has highlighted the inherent complexity related to this parameterization. Kowalik, Lassota, Majewski, Pilipczuk, and Sokolowski [28] studied the Point in Cone problem, a special case of the Cone and Polytope Intersection problem where the second polytope $\mathcal{Q}$ consists of just one point $q$ . They showed that a double exponential dependency on $d$ is unavoidable under the Exponential Time Hypothesis (ETH) when $\mathcal{P}$ has an exponential number of inequalities. This results in an ETH-tight lower bound.

Definition 2 (ETH, [15]).

The ETH conjectures that 3-SAT cannot be solved in subexponential time. Specifically, there exists a constant $\delta>0$ such that no algorithm can solve 3-SAT with $n$ variables in time $2^{\delta n}$ .

As proven in [16], this implies that there is no algorithm for 3-SAT with running time $2^{o(n+m)}$ , where $m$ denotes the number of clauses in the formula; see also Theorem 14.4 in [4].

Furthermore, the structure of solutions to the Bin Packing problem with $d$ item sizes is known to be complex. Eisenbrand and Shmonin [6] proved via an elegant combinatorial argument that there is always an optimal solution for Bin Packing with a support (the number of distinct configurations needed) bounded by $2^{d}$ . Recently, Jansen, Pirotton, and Tutas [22] showed that the support of any optimal solution in a Bin Packing instance can be exponential in $d$ . This structural hardness provides further evidence that a double exponential runtime may be optimal.

Our Contribution

We answer the open problem above by confirming that the double exponential runtime in Goemans and Rothvoss [11] is necessary for Bin Packing, assuming the ETH. Thus, their algorithm is asymptotically optimal regarding XP time algorithms parameterized by $d$ .

Theorem 3.

There is no algorithm solving high-multiplicity Bin Packing with $d$ distinct item sizes in time ${{|I|}^{2}}^{o(d)}$ , unless the ETH fails.

We note that this does not answer whether Bin Packing is FPT with respect to $d$ . However, our result shows that any algorithm with runtime $f(d)\cdot{|I|}^{O(1)}$ must have $f(d)={2^{2}}^{\Omega(d)}$ .

To achieve this result, we reduce 3-SAT with $n$ variables to Bin Packing using an Integer Linear Program (ILP) formulation. While introducing new techniques that might also be interesting to achieve other lower bounds, we make use of known results and adapt them for our purpose. We now briefly describe the key components of our reduction.

First, we demonstrate that we may assume each variable in our 3-SAT instance occurs exactly twice positively and once negatively. This technique is an extension of [36] where only the number of occurrences of a variable is restricted to three, regardless of literal polarity. Next, we encode the instance in a single integer $Z$ with bounded size, similar to [18, 20, 24, 30, 35]. In contrast to the prior results, our encoding enables us to efficiently extract information from this number. More precisely, using just $O(\log n)$ ILP variables and constraints, we are able to extract the clause numbers in which a variable appears. This idea stems from a discussion with Weltge. In their work [24], Kaibel and Weltge study lower bounds on sizes of ILPs without additional variables.

Altogether, we construct an ILP that only allows a certain set of solutions. These solutions are carefully constructed as they will correspond to specific Bin Packing configurations that, with a certain target vector, can model a feasible assignment to 3-SAT. Some of the constraints are already given in [22]. However, their ILP is not able to model 3-SAT. To achieve this property, we have to ensure that a single 3-SAT variable cannot be set both negatively and positively at the same time. While other reductions [18, 28, 35] also use ILP encodings, we manage to achieve a more compact encoding where the number of variables and equality constraints is only logarithmic in $n$ and the ILP allows $O(n)=O(2^{d})$ specific solutions. For instance, the number of inequality constraints in the reduction from Subset Sum with Multiplicities to Point in Cone by [28] is linear in $n$ (and exponential in $d$ ).

To transform our ILP into a Bin Packing instance, we use the aggregation technique in [22]. Then, we determine the satisfiability of 3-SAT by solving a family of $O(n^{4})$ Bin Packing instances, denoted as $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ . Here $\boldsymbol{\hat{\chi}}$ is a vector containing additional, in polynomial time computable, information of a valid 3-SAT solution; for example, the component $\hat{\chi}_{3}$ represents how many variables are set to false.

The compact encoding of 3-SAT and the construction of feasible solutions allow us to translate the $2^{o(n)}$ lower bound for 3-SAT into the desired ${{|I|}^{2}}^{o(d)}$ lower bound for Bin Packing. It is worth noting that we require the sizes of the Bin Packing instance to be encoded in binary due to large item sizes. We firmly believe that this reduction technique, particularly the flexible encoding via an ILP, is of independent interest. It demonstrates a powerful pattern for establishing lower bounds that can likely be adapted to prove similar results for other problems, such as for high multiplicity ILPs with few constraints, $m$ -dimensional knapsack, multiple knapsack, scheduling problems, and high multiplicity block structured $n$ -fold and $2$ -stage ILPs. Other examples of a double exponential lower bounds under the ETH are given in [5, 7, 14, 18, 27, 28, 29, 31].

2 Preliminaries

Before presenting our main result, we establish the notation, definitions, and concepts used throughout the paper. For $n\in\mathbb{Z}_{\geq 1}$ , we define $[n]\coloneqq\{1,2,\ldots,n\}$ and $[n]_{0}\coloneqq\{0,1,\ldots,n-1\}$ . For a vector $\boldsymbol{x}\in\mathbb{Z}^{n}$ , we denote its components by $x_{1},x_{2},\ldots,x_{n}$ . We also use a convenient notation for vectors. For example, if $\boldsymbol{x}=(x_{1},\ldots,x_{n})\in\mathbb{Z}^{n}$ and $a,b,c\in\mathbb{Z}$ , then $\boldsymbol{y}=(\boldsymbol{x},a,b,c)$ denotes the vector $(x_{1},\ldots,x_{n},a,b,c)$ . As our reduction is from 3-SAT, we formally define this problem here:

Definition 4 (3-SAT).

Given $n\in\mathbb{Z}_{\geq 0}$ boolean variables $v_{i},i\in[n]_{0}$ and a boolean formula $\varphi=C_{0}\land C_{1}\land\cdots\land C_{m-1},m\in\mathbb{Z}_{\geq 0}$ , where each clause $C_{j}$ consists of at most three literals, e.g., $C_{j}=(\ell_{j1}\lor\ell_{j2}\lor\ell_{j3})$ . A literal $\ell_{jk}$ is either a variable $v_{i}$ or its negation $\lnot v_{i}$ for some $i\in[n]_{0}$ . The 3-SAT problem asks whether there exists an assignment $\phi:\{v_{0},\ldots,v_{n-1}\}\mapsto\{\texttt{true},\texttt{false}\}$ that satisfies the formula $\varphi$ .

The concept of a well-structured 3-SAT instance is central to many reductions in complexity theory, especially when aiming for tight lower bounds. Tovey [36] introduced a transformation that converts any 3-SAT instance into an equivalent one with at most $3$ occurrences per variable. We use a slight extension of this transformation to obtain instances where each variable appears exactly twice positively and once negatively. Similar transformations have also been used in other reductions [2, 21].

Lemma 5 (✀, Well-Structured 3-SAT; Extension of [36]).

Given any instance of 3-SAT with $n$ variables and $m=O(n)$ clauses, there exists an equivalent instance with $n^{\prime}=O(n)$ variables and $m^{\prime}=O(n)$ clauses, where each variable $v_{i}$ has exactly two positive appearances in the clauses and exactly one negative appearance.

Proof.

A formal proof is given in the full version for completeness. $\hfill\blacktriangleleft$

In this work, we construct a non-trivial ILP. Whenever a constraint is indexed by a solid star (e.g., ★ C1), it indicates that the constraint is nonlinear. Similarly, a non-solid star (☆) denotes a constraint that is linear but not yet in its equality form. We state these purely for readability. By applying standard techniques, such as adding slack variables or using the conversions captured in the next lemma, we transform them into linear equality constraints. The full set of final equality constraints is listed in Section B.2, where each unstarred constraint shares the exact same number as its starred counterpart in the main text (e.g., the final form of ★ C1 is C1).

Linearization of quadratic terms has been extensively studied in the context of $0-1$ quadratic programming (BQP) and quadratic integer programming (QIP) with the original work going back to [32]. Quadratic terms $x\cdot y$ with Boolean and integer variables $x, y$ can be replaced using additional variables and/or inequalities; see also [8, 10, 32]. For example, if $x, y$ are both Boolean variables, then $z=x\cdot y$ can be replaced by

\displaystyle z\leq x,\ z\leq y,\ z\geq x+y-1,\text{ and }z\geq 0.

If $x\in\{0,1\}$ and $y\in[L,U]$ and $y$ integral, then $z=x\cdot y$ can be replaced by

\displaystyle z\leq y,\ z\leq U\cdot x,\ z\geq L\cdot x,\text{ and }z\geq y+(x% -1)\cdot U.

We show how to linearize such terms without the introduction of new variables under certain conditions. The fact that we can linearize these constraints without introducing additional variables enables us to reason using equivalent nonlinear constraints.

Lemma 6 (✀).

The nonlinear equation $y=\sum_{j=1}^{k}{x_{j}\cdot\chi_{j}}$ involving integer variables $x_{j}$ with known bounds $0\leq x_{j}\leq U$ and binary variables $\chi_{j}\in\{0,1\}$ with $\sum_{j=1}^{k}\chi_{j}\leq 1$ can be equivalently expressed using $O(k)$ linear inequalities and no additional variables.

Proof.

We provide the proof of this lemma in the full version. $\hfill\blacktriangleleft$

Another key concept at the core of our reduction is the ILP aggregation. For this, we have to transform each linear inequality constraint into one equality constraint through the introduction of slack variables. While the general concept of an ILP aggregation is not new, recently Jansen, Pirotton, and Tutas [22] presented a new technique allowing them to integrate upper bounds on variables into the aggregation. We summarize this result:

Lemma 7 ([22]).

Let $d,k=O(\log n)$ . Consider an ILP $A\boldsymbol{x}=\boldsymbol{b}$ , with $\boldsymbol{x}\in\mathbb{Z}_{\geq 0}^{d}$ , $\boldsymbol{x}\leq\boldsymbol{u}$ with $A=(a_{ij})_{i\in[k],j\in[d]}\in\mathbb{Z}^{k\times d}$ , $\boldsymbol{u}\in\mathbb{Z}_{\geq 0}^{d}$ and $\boldsymbol{b}\in\mathbb{Z}^{k}$ and let $\Delta\coloneqq\|A\|_{\infty}$ be the largest absolute value in $A$ . The vector $\boldsymbol{x}$ is a feasible integer solution to the ILP $A\boldsymbol{x}=\boldsymbol{b}$ , if and only if there exists a unique $\boldsymbol{y}\in\mathbb{Z}_{\geq 0}^{d+1}$ such that $(\boldsymbol{x},\boldsymbol{y})$ is a feasible integer solution to

\begin{array}[]{l}\sum_{i=1}^{k}\big(M^{i-1}\sum_{j=1}^{d}(a_{ij}x_{j})\big)+% \sum_{j=1}^{d}\big(M^{k+j-1}(x_{j}+y_{j})\big)+M^{k+d}\big(\sum_{j=1}^{d}(x_{j% }+y_{j})+y_{d+1}\big)\\ =\sum_{i=1}^{k}(M^{i-1}b_{i})+\sum_{j=1}^{d}\big(M^{k+j-1}u_{j}\big)+M^{k+d}U,% \end{array}

(1)

where $U\coloneqq\sum_{j=1}^{d}u_{j}$ and $M\coloneqq\Delta U+\max(\|\boldsymbol{b}\|_{\infty},\|\boldsymbol{u}\|_{\infty% })+\Delta+2$ .

Proof Sketch.

Given an ILP of the form $A\boldsymbol{x}=\boldsymbol{b},\boldsymbol{x}\in\mathbb{Z}_{\geq 0}^{d},% \boldsymbol{x}\leq\boldsymbol{u}$ , we first replace the external upper bounds $\boldsymbol{x}\leq\boldsymbol{u}$ by $d$ constraints $x_{j}+y_{j}=u_{j},\forall j\in[d]$ , while introducing non-negative integer slack variables $y_{j}\in\mathbb{Z}_{\geq 0}$ . Additionally, we add a constraint that upper bounds the upper bounds, i.e. $\sum_{j=1}^{d}u_{j}+y_{d+1}=U$ , with $U\coloneqq\sum_{j=1}^{d}u_{j}$ and $y_{d+1}\in\mathbb{Z}_{\geq 0}$ . Next, we define the large base number $M\coloneqq\Delta U+\max(\|\boldsymbol{b}\|_{\infty},\|\boldsymbol{u}\|_{\infty% })+\Delta+2$ that prevents carries when the constraints are aggregated. Now, we multiply each constraint by a power of $M$ , i.e., we multiply the first constraint by 1, the second one by $M$ , the third by $M^{2}$ and so on. Finally, we sum up all weighted equations to Equation 1.

Since $M$ is sufficiently large, each constraint can be seen as a single base- $M$ integer. Therefore, a feasible solution $\boldsymbol{x}$ to the original ILP is also a feasible solution to the aggregated one (while adding the unique slack variables) and the two systems are equivalent. $\hfill\blacktriangleleft$

For the full proof and the equivalence of both ILPs (i.e., $\boldsymbol{x}$ is a feasible integral solution to $A\boldsymbol{x}=\boldsymbol{b}$ , $0\leq\boldsymbol{x}\leq\boldsymbol{u}$ , if and only if $(\boldsymbol{x},\boldsymbol{y})$ is a feasible integer solution with $\boldsymbol{x},\boldsymbol{y}\geq 0$ to Equation 1), we refer to Section 3 in [22]. Note that this ILP aggregation is different to the technique in [19] where they reduce c-Unary Bin Packing, i.e., Unary Bin Packing with $c$ dimensions to Unary Bin Packing with one dimension. Here the authors prove that Unary Bin Packing is W[1]-hard, parameterized by the number of bins by first reducing Subgraph Isomorphism to 10-Unary Bin Packing and then using a reduction to Unary Bin Packing. This approach relies on sophisticated methods based on k-non-averaging sets and sumfree sets. Our reduction heavily relies on the extension of the ILP constructed in [22], thus we capture the main properties of their construction in the following lemma:

Lemma 8 (✀, [22]).

For any $\gamma>\mathbb{Z}_{\geq 2}$ , there exists an ILP formulation $A\boldsymbol{x}=\boldsymbol{b}$ , with exactly $n$ unique solutions that can be computed in polynomial time and where the first $\log(n)+1$ coordinates of each solution form the following set:

X=\left\{\left(x_{1}^{\texttt{bin}},x_{2}^{\texttt{bin}},\ldots,x_{\log n}^{% \texttt{bin}},\gamma^{\sum_{\ell=1}^{\log n}{2^{\log(n)-\ell}\cdot x_{\ell}^{% \texttt{bin}}}}\right)\Big|x_{\ell}^{\texttt{bin}}\in\{0,1\}\right\},

with $\boldsymbol{x},\boldsymbol{b}\in\mathbb{Z}_{\geq 0}^{O(\log n)}$ , and $\|A\|_{\infty}\leq{\gamma^{2}}^{\log n}$ .

Proof Sketch.

The above set of solutions can be represented by the following set of nonlinear constraints with $\tilde{r}_{0}=1$ :

\displaystyle\tilde{r}_{\ell}

\displaystyle=\tilde{r}_{\ell-1}\left(1+(\gamma^{2^{\log(n)-\ell}}-1)x^{% \texttt{bin}}_{\ell}\right)

\displaystyle\forall\ell\in[\log n]

(★ C1)

For the full list of linear constraints with the desired properties and the proof of correctness, we refer to Section B.2 (denoted as (C1)) and the original work [22], respectively. $\hfill\blacktriangleleft$

3 Reduction from 3-SAT to Bin Packing

We aim to prove via reduction from 3-SAT to Bin Packing that there is no algorithm with a runtime of ${|I|}^{2^{o(d)}}$ for Bin Packing, unless the ETH fails.

Consider an arbitrary 3-SAT instance with $n$ variables and $m$ clauses. We apply a series of simplifying transformations. First, by the Sparsification Lemma [15] we can assume that $m=O(n)$ . Next, we apply Lemma 5, such that each variable now appears positively in exactly two clauses and negatively in exactly one clause. This transformation runs in polynomial time and does not significantly increase the number of variables and clauses, so we still have $m=O(n)$ . Finally, to simplify the notation, we assume w.l.o.g. that the number of variables $n$ is a power of two. If $n$ is not $2^{k}$ for some integer $k$ , we repeatedly add a new variable $v_{n}$ and the trivially true clause $(v_{n}\lor v_{n}\lor\lnot v_{n})$ until the number of variables is a power of two. Now denote this well-structured 3-SAT instance as $\mathcal{I}^{\texttt{SAT}}$ .

In preparation for the reduction, we encode the 3-SAT instance $\mathcal{I}^{\texttt{SAT}}$ in a single large integer $Z$ . Similar techniques have been used in other reductions [18, 20, 24, 30, 35]; however, our encoding is structurally simpler than previous approaches. Furthermore, we efficiently extract specific information from $Z$ ; to our knowledge, such a method has not been previously utilized.

The general idea is to construct a large (base $\gamma^{m}$ ) integer with three dedicated “digits” for each variable $v_{i}$ that encode the clauses in which $v_{i}$ appears positively and negatively. To that end, let $j,k\in[m]_{0}$ be the clauses where $v_{i}$ appears positively and let $\ell\in[m]_{0}$ be the clause where $v_{i}$ appears negatively. We define $C_{pos1}^{(i)}\coloneqq\gamma^{j}$ , $C_{pos2}^{(i)}\coloneqq\gamma^{k}$ , and $C_{neg\vphantom{p2}}^{(i)}\coloneqq\gamma^{\ell}$ , with $\gamma\in\mathbb{Z}_{>3}$ . Later, we will set $\gamma=4n+1$ ; however, for the following lemmas this is not required.

Lemma 9.

A well-structured 3-SAT instance with $n$ variables and $m$ clauses can be represented as an integer $Z$ of size at most $\gamma^{3nm}$ with $\gamma\in\mathbb{Z}_{>3}$ , such that

\displaystyle Z=\sum_{i=0}^{n-1}\left((\gamma^{m})^{3i}\cdot C_{pos1}^{(i)}+(% \gamma^{m})^{3i+1}\cdot C_{pos2}^{(i)}+(\gamma^{m})^{3i+2}\cdot C_{neg% \vphantom{p2}}^{(i)}\right).

(2)

The integer $Z$ can be computed in polynomial time.

Proof.

First, we verify that $Z\leq\gamma^{3nm}$ . The expression for $Z$ can be viewed as a number represented in base $\gamma^{m}$ with $3n$ digits. We obtain the following upper bound for $Z$

\displaystyle Z\leq\sum_{i=0}^{3n-1}(\gamma^{m}-1)\cdot(\gamma^{m})^{i}=(% \gamma^{m}-1)\sum_{i=0}^{3n-1}(\gamma^{m})^{i}=(\gamma^{m}-1)\frac{(\gamma^{m}% )^{3n}-1}{\gamma^{m}-1}<\gamma^{3nm}.

From the definition of a well-structured 3-SAT instance, we know that each variable $v_{i},i\in[n]_{0}$ appears in exactly three clauses: Twice positively (in the clauses $j, k$ ) and once negatively (in clause $\ell$ ). Note that these indices can be found in polynomial time by iterating through all clauses. Defining $C_{pos1}^{(i)}:=\gamma^{j},C_{pos2}^{(i)}:=\gamma^{k},C_{neg\vphantom{p2}}^{(i% )}:=\gamma^{\ell}$ can be done by scanning over all clauses for all $i\in[n]_{0}$ .

Next, we compute $Z$ from these terms. The expression for $Z$ can be computed efficiently using $O(n)$ multiplications and $O(n)$ additions. Let $k$ be the bit-length of $\gamma^{m}$ and the $C^{(i)}$ terms. The computation involves a sequence of $O(n)$ multiplications where the intermediate sum’s bit-length grows linearly. The $j$ -th multiplication for $j\in\{1,\ldots,O(n)\}$ multiplies an intermediate sum of $O(j\cdot k)$ bits by $\gamma^{m}$ . Using naive $O(k^{2})$ multiplication, this step takes $O((j\cdot k)k)$ time. The total sum for this summation is the sum of all $O(n)$ steps, i.e.,

\displaystyle\sum_{j=1}^{O(n)}O(j\cdot k^{2})=O(k^{2})\sum_{j=1}^{O(n)}j=O(k^{% 2}\cdot n^{2}).

Substituting $k=O(m\log\gamma)$ , this results in $O(n^{2}m^{2}\log^{2}\gamma)$ . This completes the proof. $\hfill\blacktriangleleft$ Note that the time complexity can be improved significantly by using the $O(k\log k)$ time multiplication algorithm by Harvey and van der Hoeven [13] and/or exploiting the fact that all involved terms are a power of two.

3.1 Construction of the ILP

The core of our reduction is an ILP formulation with a carefully crafted solution structure. Later, each solution of this ILP will correspond to one of five configuration types for the Bin Packing problem. These configuration types represent different ways a 3-SAT variable can satisfy clauses. The high-level idea is as follows: Suppose, for each $i\in[n]_{0}$ we have to select exactly two of the following five solution types in $\mathcal{X}^{(i)}$ such that the sum of all selected solutions equals a target vector $\boldsymbol{t}$ .

\displaystyle\mathcal{X}^{(i)}=\left\{\begin{pmatrix}C^{(i)}_{pos1}\\ \gamma^{i}\\ 0\\ \end{pmatrix},\begin{pmatrix}C^{(i)}_{pos2}\\ \gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}C^{(i)}_{neg\vphantom{p2}}\\ 2\cdot\gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ \gamma^{i}\\ 1\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ 0\\ 1\end{pmatrix}\right\},\quad\quad\boldsymbol{t}=\begin{pmatrix}\sum_{j=0}^{m-1% }{\gamma^{j}}\\ \sum_{i=0}^{n-1}{2\cdot\gamma^{i}}\\ 2n-m\end{pmatrix}

Recall that $C_{pos1}^{(i)},C_{pos2}^{(i)},C_{neg\vphantom{p2}}^{(i)}$ are of the form $\gamma^{j}$ , thus when $\gamma$ is sufficiently large, the first coordinate of $\boldsymbol{t}$ ensures that each clause $j\in[m]_{0}$ is selected (satisfied) exactly once. The last two coordinates ensure a consistent assignment of the variables. We formally show this later.

In the remainder of this work, given an integer $i\in[n]_{0}$ , we refer to the binary encoding of $i$ as $\boldsymbol{x^{\texttt{bin}}}=(x^{\texttt{bin}}_{1},\ldots,x^{\texttt{bin}}_{% \log n})$ , with $i=\sum_{\ell=1}^{\log n}2^{\log(n)-\ell}\cdot x_{\ell}^{\texttt{bin}}$ .

The foundation of our ILP construction is the formulation in Lemma 8, which uses $O(\log n)$ variables and constraints to create $n$ distinct solution vectors. Specifically, for each $i\in[n]_{0}$ there exists a unique solution to (★ C1) where the variable $\tilde{r}_{\log n}=\gamma^{i}$ and the variables $x_{1}^{\texttt{bin}},\ldots,x_{\log n}^{\texttt{bin}}$ represent the binary encoding of $i$ .

We extend the ILP given by (★ C1) as described in the following theorem:

Theorem 10.

Given a well-structured 3-SAT encoding $Z$ as defined in Equation 2, there exists an ILP formulation $A\boldsymbol{x}\leq\boldsymbol{b}$ with variable vector $\boldsymbol{x}=(\boldsymbol{\alpha},\boldsymbol{\beta},\boldsymbol{\chi})^{% \intercal}\in\mathbb{Z}_{\geq 0}^{O(\log n)}$ and right-hand side $\boldsymbol{b}\in\mathbb{Z}^{O(\log n)}$ that has exactly $5n$ solutions.

These solutions are partitioned into $n$ groups of $5$ , indexed by $i\in[n]_{0}$ . For each index $i$ , the subvector $\boldsymbol{\alpha}$ takes exactly one of the following $5$ distinct assignments:

\boldsymbol{\alpha}=\begin{pmatrix}\alpha_{1}\vphantom{C^{(i)}_{pos1}}\\ \alpha_{2}\vphantom{\gamma^{i}}\\ \alpha_{3}\end{pmatrix}\in\left\{\begin{pmatrix}C^{(i)}_{pos1}\\ \gamma^{i}\\ 0\\ \end{pmatrix},\begin{pmatrix}C^{(i)}_{pos2}\\ \gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}C^{(i)}_{neg\vphantom{p2}}\\ 2\cdot\gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ \gamma^{i}\\ 1\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ 0\\ 1\end{pmatrix}\right\}.

For each index $i$ , the corresponding subvector $\boldsymbol{\beta}\in\mathbb{Z}_{\geq 0}^{O(\log n)}$ is uniquely determined (depending solely on $i$ and $Z$ ) and is computable in polynomial time. Finally, the subvector $\boldsymbol{\chi}$ always satisfies $\boldsymbol{\chi}\in\{0,1\}^{O(1)}$ .

We achieve this result through the introduction of $O(\log n)$ constraints, $O(\log n)$ auxiliary variables $\boldsymbol{\beta}$ , and 4 binary variables $\boldsymbol{\chi}=(\chi_{1},\ldots,\chi_{4})$ . For improved readability, we deviate from a strict component-wise notation (e.g. $\boldsymbol{\beta}=(\beta_{1},\beta_{2},\ldots)$ ) and will implicitly include all introduced auxiliary variables within the vector $\boldsymbol{\beta}$ , unless explicitly stated otherwise. In particular, we include variables in constraint (★ C1) in this vector (e.g. $\boldsymbol{\beta}=(\tilde{r}_{0},\ldots,\tilde{r}_{\log n},\boldsymbol{x}^{% \texttt{bin}},\ldots)$ ). The values of these variables are unique for fixed $i, Z$ , as shown in [22]. For all newly introduced variables, we argue this property separately.

In order to construct the desired solutions for $\boldsymbol{\alpha}$ , the clauses relevant for the 3-SAT variable $v_{i}$ (i.e., $C^{(i)}_{pos1},C^{(i)}_{pos2},C^{(i)}_{neg\vphantom{p2}}$ ) need to be extracted from $Z$ . We can achieve this efficiently since the variables $x^{\texttt{bin}}_{1},\ldots,x^{\texttt{bin}}_{\log n}$ already represent the binary encoding of $i$ , and thus describe the path through a binary search tree to reach the $i$ -th block of $Z$ . This idea could also be useful to compactly encode other problems in ILP formulations. The following constraints extract the corresponding block from $Z$ into a variable $z_{\log n}$ . Again, we list the equivalent linear constraints in Section B.2 and focus on the nonlinear version for improved readability. An example procedure is illustrated in Figure 1.

$\displaystyle z_{0}$	$\displaystyle=Z$		(C2)
$\displaystyle z_{j}$	$\displaystyle=q_{j}\cdot(\gamma^{m})^{3n/2^{j+1}}+r_{j}$	$\displaystyle\forall j\in[\log n]_{0}$	(C3)
$\displaystyle r_{j}$	$\displaystyle\leq(\gamma^{m})^{3n/2^{j+1}}-1$	$\displaystyle\forall j\in[\log n]_{0}$	(☆ C4)
$\displaystyle z_{j+1}$	$\displaystyle=q_{j}\cdot x^{\texttt{bin}}_{j+1}+r_{j}\cdot(1-x^{\texttt{bin}}_% {j+1})$	$\displaystyle\forall j\in[\log n]_{0}$	(★ C5)

For the proofs of Claims 11–13, we refer the reader to Section A.1.

Claim 11 (✀).

The constraints given in Equations C2–★ C5 ensure that $z_{\log n}$ contains exactly the block of $Z$ corresponding to variable $v_{i}$ , i.e., for $i\in[n]_{0}$ we get $z_{\log n}=C^{(i)}_{pos1}\cdot(\gamma^{m})^{0}+C^{(i)}_{pos2}\cdot(\gamma^{m})% ^{1}+C^{(i)}_{neg\vphantom{p2}}\cdot(\gamma^{m})^{2}$ . Additionally, the values of all introduced variables are unique for fixed $i$ and $Z$ .

Figure 1: Extraction of the block corresponding to variable

v_{1}

(

\boldsymbol{x}^{\texttt{bin}}=(0,1)

) with Constraints (C2) to (★ C5).

Extracting the values $C^{(i)}_{pos1},C^{(i)}_{pos2},C^{(i)}_{neg\vphantom{p2}}$ into auxiliary variables $c_{pos1},c_{pos2},c_{neg}$ can be done with the following constraints:

$\displaystyle z_{\log n}$	$\displaystyle=q_{c}\cdot\gamma^{m}+c_{pos1}$	(C6)
$\displaystyle q_{c}$	$\displaystyle=c_{neg}\cdot\gamma^{m}+c_{pos2}$	(C7)
$\displaystyle c_{pos1},c_{pos2},c_{neg}$	$\displaystyle\leq\gamma^{m}-1$	(☆ C8)

Claim 12 (✀).

The constraints given in Equations C2–☆ C8 ensure that the variables $c_{pos1},c_{pos2}$ and $c_{neg}$ match the corresponding values in the definition of $Z$ in Equation 2 for a given $i$ , i.e., $c_{pos1}=C^{(i)}_{pos1},c_{pos2}=C^{(i)}_{pos2}$ and $c_{neg}=C^{(i)}_{neg\vphantom{p2}}$ . Additionally, the values of all introduced variables are unique for fixed $i$ and $Z$ .

Using these auxiliary variables, we define the solution values for $\boldsymbol{\alpha}$ , as required by Theorem 10. This construction utilizes binary variables $\alpha_{3},\chi_{1},\chi_{2},\chi_{3},\chi_{4}\in\{0,1\}$ and integer variables $\alpha_{1},\alpha_{2}$ :

$\displaystyle\alpha_{1}$	$\displaystyle=c_{pos1}\cdot\chi_{1}+c_{pos2}\cdot\chi_{2}+c_{neg}\cdot\chi_{3}$	(★ C9)
$\displaystyle\alpha_{2}$	$\displaystyle=\tilde{r}_{\log n}\cdot\chi_{1}+\tilde{r}_{\log n}\cdot\chi_{2}+% 2\cdot\tilde{r}_{\log n}\cdot\chi_{3}+\tilde{r}_{\log n}\cdot\chi_{4}$	(★ C10)
$\displaystyle 1-\alpha_{3}$	$\displaystyle=\chi_{1}+\chi_{2}+\chi_{3}$	(C11)
$\displaystyle\chi_{4}$	$\displaystyle\leq\alpha_{3}$	(☆ C12)

Claim 13 (✀).

For $i\in[n]_{0}$ , the constraints given in Equations C2–☆ C12 imply that

\displaystyle\begin{pmatrix}\alpha_{1}\vphantom{C^{(i)}_{pos1}}\\ \alpha_{2}\vphantom{\gamma^{i}}\\ \alpha_{3}\end{pmatrix}\in\left\{\begin{pmatrix}C^{(i)}_{pos1}\\ \gamma^{i}\\ 0\\ \end{pmatrix},\begin{pmatrix}C^{(i)}_{pos2}\\ \gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}C^{(i)}_{neg\vphantom{p2}}\\ 2\cdot\gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ \gamma^{i}\\ 1\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ 0\\ 1\end{pmatrix}\right\}.

All other introduced variables are binary (part of $\boldsymbol{\chi}$ ).

As established in Claims 11, 12, and 13, the desired properties for $\boldsymbol{\alpha}$ (see Theorem 10) can be enforced by a compact nonlinear system with $O(\log n)$ variables and $O(\log n)$ constraints. Our goal is to linearize this system while preserving its compact size. First, we address (★ C1), providing its equivalent linear formulation in Section B.2. For this specific subsystem, [22] showed that all variables remain unique for any fixed $i$ . This leaves the nonlinear constraints (★ C5), (★ C9), and (★ C10). We apply Lemma 6 to linearize these constraints without introducing any additional variables. Because no new variables are added during this process, the crucial uniqueness property established in Claims 11, 12, and 13 is preserved. A complete list of these final linearized constraints is provided in Appendix B. With this, we have proven Theorem 10.

3.2 Constructing the Bin Packing Instance

In the previous section, we showed how to construct a compact ILP, allowing only very specific solution vectors (see Theorem 10). Now, we show how to construct a Bin Packing instance from this ILP.

First, we aggregate the ILP from Theorem 10 into an ILP with a single knapsack constraint. To this end, we use the aggregation technique in [22] that is stated in Lemma 7. The ILP from Theorem 10 contains inequality constraints, in order to apply Lemma 7, we first transform it into an ILP with equality constraints by introducing slack variables $\boldsymbol{y}\in\mathbb{Z}^{O(\log n)}$ . We list the final equality constraints Equations C1–C12 in Section B.2 for the sake of completeness. Observe that since we introduce at most one slack variable per inequality, the number of variables and constraints remains in $O(\log n)$ .

Applying the aggregation in Lemma 7 to the ILP of form $A\boldsymbol{x}=\boldsymbol{b}$ , we obtain an ILP with a single linear constraint of the form $\boldsymbol{s}^{\intercal}\boldsymbol{x}=B$ where $\boldsymbol{x}=(\boldsymbol{\alpha},\boldsymbol{\beta},\boldsymbol{\chi},% \boldsymbol{y})^{\intercal}$ . Note that the aggregation adds $O(\log(n))$ extra slack variables to the slack variable vector $\boldsymbol{y}$ . Thus, we still have $\boldsymbol{s},\boldsymbol{x}\in\mathbb{Z}^{O(\log n)}$ . Recall, that $\boldsymbol{\alpha}$ contains three variables and $\boldsymbol{\beta}=(\boldsymbol{x}^{\texttt{bin}},\tilde{\boldsymbol{r}},% \boldsymbol{z},\boldsymbol{q},\boldsymbol{r},c_{pos1},c_{pos2},c_{neg},% \boldsymbol{y},\ldots)\in\mathbb{Z}^{O(\log n)}$ is the variable vector containing all variables with unique values for any fixed $i, Z$ (see Theorem 10).

Lemma 14 (✀).

The aggregated ILP of the form $\boldsymbol{s}^{\intercal}\boldsymbol{x}=B$ for $\boldsymbol{x}=(\boldsymbol{\alpha},\boldsymbol{\beta},\boldsymbol{\chi},% \boldsymbol{y})$ has dimensions $\boldsymbol{s},\boldsymbol{x}\in\mathbb{Z}_{\geq 0}^{O(\log n)}$ and $||\boldsymbol{s}||_{\infty},B\leq\gamma^{O(n^{2}\log n)}$ . Furthermore, $||\boldsymbol{x}||_{\infty}\leq\gamma^{O(n^{2})}$ holds for every feasible solution $\boldsymbol{x}$ .

The above lemma is a direct application of the technique from [22] (summarized in Lemma 7), therefore, we defer the proof of this lemma to the full version.

Note that the solution vectors satisfying the equation $\boldsymbol{s}^{\intercal}\boldsymbol{x}=B$ are exactly those of the above constructed ILP (those listed in Theorem 10).

We are now ready to construct a family of Bin Packing instances $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ where $\hat{\boldsymbol{\chi}}\in\{0,\ldots,2n\}^{4}$ . Each instance has $d=O(\log n)$ item types, defined by the item size vector $\boldsymbol{s}$ and bin capacity $B$ . Intuitively, this implies that for any feasible configuration $\boldsymbol{x}$ , the inequation $\boldsymbol{s}^{\intercal}\boldsymbol{x}\leq B$ holds. We now set the item multiplicities $\boldsymbol{a}$ such that a Bin Packing solution is forced to select specific configurations, as we will prove later (Lemma 16). We set $\boldsymbol{a}\coloneqq(\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}},% \hat{\boldsymbol{\chi}},\hat{\boldsymbol{y}})^{\intercal}$ , where each component is a vector, to be defined in the following paragraph. The first component is set to

\displaystyle\hat{\boldsymbol{\alpha}}\coloneqq\left(\sum_{j=0}^{m-1}{\gamma^{% j}},\sum_{i=0}^{n-1}{2\cdot\gamma^{i}},2n-m\right)^{\intercal}.

(3)

Intuitively, this ensures that any solution with $2n$ bins is guaranteed to (1) select each clause, and (2) correspond to a consistent assignment of 3-SAT variables $\{v_{i}\}\mapsto\{\texttt{true},\texttt{false}\}$ . We formally prove this in Lemma 16.

Now, let $\boldsymbol{\beta}(i)$ denote the unique variable values for each ILP-variable in $\boldsymbol{\beta}$ . Note that by Theorem 10 these values are unique for each $i\in[n]_{0}$ and can be computed in polynomial time. For example, consider the variables appearing in (C2)-(★ C5). For fixed $Z$ and $x^{\texttt{bin}}_{i}$ , the values of $q_{i},r_{i}$ , and $z_{i}$ can be calculated by $O(\log n)$ Euclidean divisions. We then set

\displaystyle\hat{\boldsymbol{\beta}}\coloneqq\sum_{i=0}^{n-1}2\cdot% \boldsymbol{\beta}(i).

(4)

Let now $\mathcal{S}$ be any set of $2n$ solutions to $\boldsymbol{s}^{\intercal}(\boldsymbol{\alpha},\boldsymbol{\beta},\boldsymbol{% \chi},\boldsymbol{y})=B$ . For any variable $x_{i}$ (e.g., $\alpha_{i},c_{pos1},\chi_{i},y_{i}$ ), we define $\hat{x}_{i}$ as the sum of its values across all $2n$ solutions in $\mathcal{S}$ : $\hat{x}_{i}\coloneqq\sum_{s\in\mathcal{S}}x_{i}(s)$ . The vector $\hat{\boldsymbol{y}}$ is composed of these summed values for each of the $O(\log n)$ slack variables in $\boldsymbol{y}$ . The value of each component can be calculated from the known values of the other variables (i.e., $\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}},\hat{\boldsymbol{\chi}}$ ), since each constraint contains at most one slack variable.

We demonstrate how to calculate $\hat{\boldsymbol{y}}$ with the example of component $y^{cc}_{1}$ in the first constraint of (C9):

\displaystyle\alpha_{1}-c_{pos1}+U^{cc}\cdot\chi_{1}+y_{1}^{cc}=U^{cc}.

Here $y^{cc}_{1}$ is the single slack variable and $U^{cc}$ is a known upper bound. Then:

\begin{array}[]{crl}&\sum_{s\in\mathcal{S}}\left(\alpha_{1}(s)-c_{pos1}(s)+U^{% cc}\cdot\chi_{1}(s)+y_{1}^{cc}(s)\right)&=\sum_{s\in\mathcal{S}}U^{cc}\\ \Longleftrightarrow&\hat{\alpha}_{1}-\hat{c}_{pos1}+U^{cc}\cdot\hat{\chi}_{1}+% \hat{y}_{1}^{cc}&=2n\cdot U^{cc}.\end{array}

Since $\hat{y}_{1}^{cc}$ is the only unknown, it can be calculated. We set $\hat{\boldsymbol{y}}$ by solving each of the $O(\log n)$ constraints this way. Then, the multiplicities in instance $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ are given by: $\boldsymbol{a}=(\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}},\hat{% \boldsymbol{\chi}},\hat{\boldsymbol{y}})$ . Note that the above construction ensures $\boldsymbol{s}^{\intercal}\boldsymbol{a}=2n\cdot B$ . We also note that while it is sufficient for our analysis to consider all possibilities for $\hat{\boldsymbol{\chi}}$ , the number of considered vectors could be reduced significantly. When considering the corresponding variables $\boldsymbol{\chi}=(\chi_{1},\chi_{2},\chi_{3},\chi_{4})$ in the constructed ILP, we notice that $\hat{\chi_{1}},\hat{\chi_{2}}$ , and $\hat{\chi_{3}}$ count the number of times a clause is selected. Since we aim to choose all $m$ clauses, $\hat{\chi}_{3}=m-\hat{\chi}_{1}-\hat{\chi}_{2}$ . A similar argument can be made for $\hat{\chi}_{4}$ . This variable counts the usage of the first slack solution. This number can be calculated from $\hat{\chi}_{3}$ . These two arguments bring the number of considered vectors from $(2n+1)^{4}$ to $(2n+1)^{2}$ since only $\hat{\chi}_{1}$ and $\hat{\chi}_{2}$ need to be guessed.

The polytope defining all feasible configurations in the Bin Packing instance is given by $P=\{\boldsymbol{x}\in\mathbb{Z}_{\geq 0}^{d}|\boldsymbol{s}^{\intercal}% \boldsymbol{x}\leq B\}$ . We prepare our final proof by showing that each solution with at most $2n$ bins uses only configurations $\boldsymbol{x}$ that satisfy $\boldsymbol{s}^{\intercal}\boldsymbol{x}=B$ .

Claim 15.

Any solution to $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ with at most $2n$ bins uses only configurations $\boldsymbol{x}$ that satisfy $\boldsymbol{s}^{\intercal}\boldsymbol{x}=B$ .

Proof.

First, note that by construction of $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ , the total size of items is $\boldsymbol{s}^{\intercal}\boldsymbol{a}=2n\cdot B$ . Now, assume for the sake of contradiction that there exists a solution to the constructed Bin Packing instance with $2n$ bins that uses a configuration $\boldsymbol{x}$ with $\boldsymbol{s}^{\intercal}\boldsymbol{x}<B$ . Then, the remaining size of items is $2n\cdot B-\boldsymbol{s}^{\intercal}\boldsymbol{x}>(2n-1)\cdot B$ and thus cannot be packed into the remaining $2n-1$ bins. A contradiction. $\hfill\vartriangleleft$

Now, define the set of feasible solutions to the constructed ILP as

\displaystyle\mathcal{X}=\left\{\boldsymbol{x_{1}^{(i)}},\ldots,\boldsymbol{x_% {5}^{(i)}}=\begin{pmatrix}C^{(i)}_{pos1}\\ \gamma^{i}\\ 0\\ \boldsymbol{\beta}(i)\\ \boldsymbol{\chi}\\ \boldsymbol{y}\end{pmatrix},\begin{pmatrix}C^{(i)}_{pos2}\\ \gamma^{i}\\ 0\\ \boldsymbol{\beta}(i)\\ \boldsymbol{\chi}\\ \boldsymbol{y}\end{pmatrix},\begin{pmatrix}C^{(i)}_{neg\vphantom{p2}}\\ 2\gamma^{i}\\ 0\\ \boldsymbol{\beta}(i)\\ \boldsymbol{\chi}\\ \boldsymbol{y}\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ \gamma^{i}\\ 1\\ \boldsymbol{\beta}(i)\\ \boldsymbol{\chi}\\ \boldsymbol{y}\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ 0\\ 1\\ \boldsymbol{\beta}(i)\\ \boldsymbol{\chi}\\ \boldsymbol{y}\end{pmatrix}\,\middle|\,i\in[n]_{0}\right\}.

Claim 15 implies that any Bin Packing solution uses only configurations $\boldsymbol{x}\in\mathcal{X}$ . We are ready to prove the final lemma, stating that the 3-SAT instance $\mathcal{I}^{\texttt{SAT}}$ is solvable if and only if there exists a solution to any of the Bin Packing instances $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ . An illustration of a constructed Bin Packing instance is given in Figure 2.

Figure 2: Example for a 3-SAT instance with

2

variables

v_{0}

(pink) and

v_{1}

(yellow). The illustrated solution corresponds to the assignment

v_{0}=\texttt{true}

and

v_{1}=\texttt{false}

.

Lemma 16.

Given an integer $\gamma>4n$ , the well-structured 3-SAT instance $\mathcal{I}^{\texttt{SAT}}$ is a Yes-Instance if and only if there exists a $\hat{\boldsymbol{\chi}}\in\{0,\ldots,2n\}^{4}$ such that $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ has a solution with at most $2n$ bins.

Proof.

Let the well-structured 3-SAT instance $\mathcal{I}^{\texttt{SAT}}$ be given as in Lemma 5.

We first remember that due to the aggregation, there cannot be any carry-overs between the variable dimensions in the ILP. Therefore, when solving the Bin Packing instance, we ask how many configurations of each type to use i.e., we solve the linear combination

\displaystyle\sum_{i=0}^{n-1}\sum_{k=1}^{5}{\lambda^{(i)}_{k}\boldsymbol{x^{(i% )}_{k}}}=\boldsymbol{a}=\begin{pmatrix}\sum_{j=0}^{m-1}{\gamma^{j}}\\ \sum_{i=0}^{n-1}{2\cdot\gamma^{i}}\\ 2n-m\\ \hat{\boldsymbol{\beta}}\\ \hat{\boldsymbol{\chi}}\\ \hat{\boldsymbol{y}}\end{pmatrix}\text{, with }\sum_{i=0}^{n-1}\sum_{k=1}^{5}{% \lambda^{(i)}_{k}}\leq 2n.

For the remainder of this proof, we will refer to $\boldsymbol{x^{(i)}_{1}}$ , $\boldsymbol{x^{(i)}_{2}}$ , and $\boldsymbol{x^{(i)}_{3}}$ as clause-paying vectors and to $\boldsymbol{x^{(i)}_{4}}$ and $\boldsymbol{x^{(i)}_{5}}$ as slack vectors. Similarly, we refer to $\lambda^{(i)}_{1}$ , $\lambda^{(i)}_{2}$ , and $\lambda^{(i)}_{3}$ as clause-paying coefficients.

" $\Rightarrow$ ": We start with the “if” direction and assume that there exists a satisfying assignment $\phi:\{v_{0},\ldots v_{n-1}\}\mapsto\{\texttt{true},\texttt{false}\}$ for the 3-SAT instance. First, define a satisfier function $S:\{C_{1},\ldots,C_{m}\}\mapsto\{v_{0},\ldots,v_{n-1},\lnot v_{0},\ldots,\lnot v% _{n-1}\}$ , such that the following conditions hold:

$\blacksquare$

$S(C_{j})$ is a literal that appears in the clause $C_{j}$ and
$\blacksquare$

the literal $S(C_{j})$ evaluates to true when applying $\phi$ i.e., $\phi(S(C_{j}))=\texttt{true}$ .

Since $\phi$ is a satisfying assignment, such a function exists.

For each variable $v_{i}$ , let $j,k,\ell$ be the indices of the clauses where $v_{i}$ appears positively and negatively, respectively, i.e., $C^{(i)}_{pos1}=\gamma^{j}$ , $C^{(i)}_{pos2}=\gamma^{k}$ and $C^{(i)}_{neg\vphantom{p2}}=\gamma^{\ell}$ . Now, we set the coefficients $\lambda^{(i)}_{k}$ for each variable $v_{i}$ as follows:

Case 1: ( $\phi(v_{i})=\texttt{true}$ ). Set $\lambda^{(i)}_{1}=1$ if $S(C_{j})=v_{i}$ and similarly $\lambda^{(i)}_{2}=1$ if $S(C_{k})=v_{i}$ . Additionally, set $\lambda^{(i)}_{4}=2-(\lambda^{(i)}_{1}+\lambda^{(i)}_{2})$ . All other coefficients are set to 0.

Case 2: ( $\phi(v_{i})=\texttt{false}$ ). If $S(C_{\ell})=\lnot v_{i}$ , then set $\lambda^{(i)}_{3}=1$ and $\lambda^{(i)}_{5}=1$ . Otherwise, set $\lambda^{(i)}_{4}=2$ . All other coefficients are set to 0.

We must now verify that the constructed linear combination produces the target vector. For the first component, note that by construction each clause-paying coefficient (i.e., $\lambda^{(i)}_{1},\lambda^{(i)}_{2}$ , and $\lambda^{(i)}_{3}$ ) is set to 1 if and only if its corresponding literal was chosen by the satisfier function $S$ . Since $S$ selects exactly one literal for each clause, the sum correctly evaluates to $\sum_{j=0}^{m-1}{\gamma^{j}}$ . For the second component, we have ensured by construction of the linear combination that for each variable $v_{i}$ , $\lambda^{(i)}_{1}+\lambda^{(i)}_{2}+2\lambda^{(i)}_{3}+\lambda^{(i)}_{4}=2$ . Thus, the sum evaluates correctly to $\sum_{i=0}^{n-1}{2\cdot\gamma^{i}}$ . The third component counts the usage of slack vectors (i.e., $\boldsymbol{x^{(i)}_{4}},\boldsymbol{x^{(i)}_{5}}$ ). By construction, $\lambda^{(i)}_{1}+\lambda^{(i)}_{2}+\lambda^{(i)}_{3}+\lambda^{(i)}_{4}+% \lambda^{(i)}_{5}=2$ for each $i\in[n]_{0}$ , resulting in $2n$ vector selections in total. Since $m$ of those are clause-paying (i.e., $\boldsymbol{x^{(i)}_{1}},\boldsymbol{x^{(i)}_{2}},\boldsymbol{x^{(i)}_{3}}$ ), the number of selected slack vectors must be $2n-m$ . It remains to show the equality for the remaining components (namely $\hat{\boldsymbol{\beta}},\hat{\boldsymbol{\chi}},\hat{\boldsymbol{y}}$ ). By construction, $\hat{\boldsymbol{\beta}}\coloneqq\sum_{i=0}^{n-1}{2\cdot\boldsymbol{\beta}(i)}$ where $\boldsymbol{\beta}(i)$ denotes the vector of unique variables for any fixed $i$ . The constructed linear combination chooses exactly two vectors for each variable $i$ , therefore $\hat{\boldsymbol{\beta}}$ is hit exactly. The components $(\chi_{1},\chi_{2},\chi_{3},\chi_{4})$ have binary values in $\boldsymbol{x_{1}^{(i)}},\ldots,\boldsymbol{x_{5}^{(i)}}$ due to Theorem 10, thus they sum up to some value $\hat{\boldsymbol{\chi}}\in\{0,\ldots,2n\}^{4}$ . Let now $\hat{\boldsymbol{\chi}}$ be the correct vector. Then $\hat{\boldsymbol{y}}$ is by construction correct for any combination of $2n$ solutions to $\boldsymbol{s}^{\intercal}\boldsymbol{x}=B$ , as argued in the construction of $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ .

" $\Leftarrow$ ": For the “only if” direction, assume that there exists a non-negative integer linear combination of the vectors $\lambda^{(i)}_{k}$ that produces the target vector for some $\hat{\boldsymbol{\chi}}\in\{0,\ldots,2n\}^{4}$ .

The satisfying assignment $\phi$ can now be constructed as follows for each variable $v_{i}$ :

\displaystyle\phi(v_{i})=\begin{cases}\texttt{false},&\text{if }\lambda^{(i)}_% {3}=1\\ \texttt{true},&\text{otherwise}\end{cases}

We must now show that $\phi$ satisfies all clauses.

We first observe that since $\gamma>4n$ there are no carries between the powers of $\gamma$ in the first two components. Indeed, the constraint $\sum_{i=0}^{n-1}\sum_{k=1}^{5}\lambda^{(i)}_{k}\leq 2n$ implies $\lambda^{(i)}_{k}\leq 2n$ for each $i\in[n]_{0}$ and $k\in[5]$ . Since the maximum coefficient in the second components is $2\cdot\gamma^{i}$ , the maximum contribution to the $i$ -th power of $\gamma$ in each component is $2n\cdot 2\cdot\gamma^{i}=4n\cdot\gamma^{i}<\gamma^{i+1}$ . Note that this argument also holds for the first component since in any well-structured 3-SAT instance, each variable appears in at most three clauses, and thus $m\leq 3n<4n<\gamma$ .

The first component of the vector equation is

\displaystyle\sum_{i=0}^{n-1}\left(\lambda^{(i)}_{1}C^{(i)}_{pos1}+\lambda^{(i% )}_{2}C^{(i)}_{pos2}+\lambda^{(i)}_{3}C^{(i)}_{neg\vphantom{pos2}}\right)=\sum% _{j=0}^{m-1}{\gamma^{j}}.

(5)

Remember that the $C_{pos1}^{(i)},C_{pos2}^{(i)},C_{neg\vphantom{pos2}}^{(i)}$ terms are of the form $\gamma^{j}$ for some integer $j$ and all $\lambda^{(i)}_{k}$ are non-negative integers. Then, for each clause $j$ , there must exist exactly one $\lambda^{(i)}_{k}$ , $i\in[n]_{0},k\in[3]$ that is equal to 1. It remains to show that for each $i\in[n]_{0}$ : $\lambda^{(i)}_{3}=1\Rightarrow\lambda^{(i)}_{1}=\lambda^{(i)}_{2}=0$ , i.e., if $v_{i}$ is set to false, it is only used to satisfy the clause in which it appears negatively. To this end, consider the second component of the vector equation

\displaystyle\sum_{i=0}^{n-1}\left(\lambda^{(i)}_{1}+\lambda^{(i)}_{2}+2\cdot% \lambda^{(i)}_{3}+\lambda^{(i)}_{4}\right)\cdot\gamma^{i}=\sum_{i=0}^{n-1}{2% \cdot\gamma^{i}}.

(6)

Again, since $\gamma>4n$ , there are no carries between the powers of $\gamma$ . Thus, for each $i\in[n]_{0}$ , we must have $\lambda^{(i)}_{1}+\lambda^{(i)}_{2}+2\cdot\lambda^{(i)}_{3}+\lambda^{(i)}_{4}=2$ . This implies that if $\lambda^{(i)}_{3}=1$ , then $\lambda^{(i)}_{1}=\lambda^{(i)}_{2}=0$ . Therefore, the assignment $\phi$ is well-defined. $\hfill\blacktriangleleft$

3.3 Putting It All Together

Theorem 3. [Restated, see original statement.]

There is no algorithm solving high-multiplicity Bin Packing with $d$ distinct item sizes in time ${{|I|}^{2}}^{o(d)}$ , unless the ETH fails.

Proof.

Let $\mathcal{I}^{\texttt{SAT}}$ be a well-structured 3-SAT instance with $n$ variables. We transform $\mathcal{I}^{\texttt{SAT}}$ into a family of Bin Packing instances $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ as in Lemma 16. The encoding length of each instance $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ is defined as $|I|=O(d\cdot\log(B)+d\cdot\log(\|\boldsymbol{a}\|_{\infty}))$ . By Lemma 14 we have: $d=O(\log n)$ item types and bin capacity $B\leq\gamma^{O(n^{2}\log n)}$ . Since the amounts $\boldsymbol{a}$ are constructed to be the sum of $2n$ solutions $\boldsymbol{x}$ to the ILP, we have

\displaystyle\|\boldsymbol{a}\|_{\infty}\leq 2n\cdot\|\boldsymbol{x}\|_{\infty% }\leq 2n\cdot\gamma^{O(n^{2})}=\gamma^{O(n^{2})}.

Thus, with $\gamma=4n+1>4n$ , the encoding length of each constructed Bin Packing instance is $|I|=O(\log n\cdot(n^{2}\log(n)^{2})+\log n\cdot n^{2}\log n)=O(n^{2}(\log n)^{% 3})$ .

Now suppose there exists an algorithm for Bin Packing with a runtime of ${|I|}^{2^{o(d)}}$ . Then, we can solve $\mathcal{I}^{\texttt{BP}}(\hat{\boldsymbol{\chi}})$ for all $\hat{\boldsymbol{\chi}}\in\{0,\ldots,2n\}^{4}$ in time $(2n+1)^{4}\cdot{|I|}^{2^{o(d)}}=(2n+1)^{4}\cdot(n^{2}(\log n)^{3})^{2^{o(d)}}=% (2n+1)^{4}\cdot(n^{2}(\log n)^{3})^{n^{o(1)}}$ . Using a similar argument as in [28], we get:

\displaystyle(2n+1)^{4}\cdot(n^{2}(\log n)^{3})^{n^{o(1)}}\leq 2^{n^{o(1)}3% \log(n)+4\log(2n+1)}\leq 2^{o(n)}

contradicting the ETH. With this, we have proven Theorem 3. $\hfill\blacktriangleleft$

4 Conclusion

Our result still leaves unresolved the central open problem of whether there exists an FPT algorithm for Bin Packing parameterized by $d$ . Goemans and Rothvoss [11] as well as Mnich and van Bevern [34] posed it as an open problem whether bin packing with $d$ item sizes can be solved in time $f(d)\cdot O(\log\Delta)^{O(1)}$ , where $f$ is an arbitrary function. Interestingly, an FPT algorithm using at most $OPT+1$ bins is known by Jansen and Solis-Oba [23].

Our techniques might be of interest when proving double exponential lower bounds for other high-multiplicity scheduling problems [11] or high-multiplicity n-folds [11, 25, 26]. Forall-exist statements are also tightly connected to this topic. In such problems, we are given a convex set $\mathcal{Q}\subseteq\mathbb{R}^{m}$ and an integer matrix $W\in\mathbb{Z}^{m\times n}$ . A major open problem is whether any algorithm solving $\forall b\in\mathcal{Q}\cap\mathbb{Z}^{m}\ \exists x\in\mathbb{Z}^{n}$ such that $Wx\leq b$ must necessarily have double-exponential running time in $n$ [1].

References

[1] Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, and Robert Weismantel. Forall-exist statements in pseudopolynomial time. In SODA, pages 2225–2233. SIAM, 2025. doi:10.1137/1.9781611978322.73.
[2] Piotr Berman, Marek Karpinski, and Alexander D. Scott. Computational complexity of some restricted instances of 3-sat. Discret. Appl. Math., 155(5):649–653, 2007. doi:10.1016/j.dam.2006.07.009.
[3] William J. Cook, Mark Hartmann, Ravi Kannan, and Colin McDiarmid. On integer points in polyhedra. Comb., 12(1):27–37, 1992. doi:10.1007/BF01191202.
[4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[5] Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM J. Comput., 45(1):67–83, 2016. doi:10.1137/130947076.
[6] Friedrich Eisenbrand and Gennady Shmonin. Carathéodory bounds for integer cones. Oper. Res. Lett., 34(5):564–568, 2006. doi:10.1016/j.orl.2005.09.008.
[7] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms, 15(1):9:1–9:27, 2019. doi:10.1145/3280824.
[8] Robert Fortet. Applications de l’algebre de boole en recherche opérationelle. Revue Française de Recherche Opérationelle, 4(14):17–26, 1960.
[9] Paul C Gilmore and Ralph E Gomory. A linear programming approach to the cutting-stock problem. Operations research, 9(6):849–859, 1961. doi:10.1287/opre.9.6.849.
[10] Fred W. Glover and Eugene Woolsey. Technical note - converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res., 22(1):180–182, 1974. doi:10.1287/opre.22.1.180.
[11] Michel X. Goemans and Thomas Rothvoss. Polynomiality for bin packing with a constant number of item types. J. ACM, 67(6):38:1–38:21, 2020. doi:10.1145/3421750.
[12] Mark E. Hartmann. Cutting planes and the complexity of the integer hull. Technical report, Cornell University, September 1988. URL: https://hdl.handle.net/1813/8702.
[13] David Harvey and Joris van der Hoeven. Integer multiplication in time o(nlog n). Annals of Mathematics, 193(2):563–617, 2021. doi:10.4007/annals.2021.193.2.4.
[14] Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, and Asaf Levin. Tight lower bounds for block-structured integer programs. Math. Program., 2025. doi:10.1007/s10107-025-02296-z.
[15] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In 39th Annual Symposium on Foundations of Computer Science, FOCS, pages 653–663. IEEE Computer Society, 1998. doi:10.1109/SFCS.1998.743516.
[16] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.
[17] Klaus Jansen and Kim-Manuel Klein. About the structure of the integer cone and its application to bin packing. Math. Oper. Res., 45(4):1498–1511, 2020. doi:10.1287/moor.2019.1040.
[18] Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota. The double exponential runtime is tight for 2-stage stochastic ilps. Math. Program., 197(2):1145–1172, 2023. doi:10.1007/s10107-022-01837-0.
[19] Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci., 79(1):39–49, 2013. doi:10.1016/J.JCSS.2012.04.004.
[20] Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discret. Math., 30(1):343–366, 2016. doi:10.1137/140952636.
[21] Klaus Jansen and Haiko Müller. The minimum broadcast time problem for several processor networks. Theor. Comput. Sci., 147(1&2):69–85, 1995. doi:10.1016/0304-3975(94)00230-G.
[22] Klaus Jansen, Lis Pirotton, and Malte Tutas. The support of bin packing is exponential. In 33rd Annual European Symposium on Algorithms, ESA 2025, LIPIcs, pages 48:1–48:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.48.
[23] Klaus Jansen and Roberto Solis-Oba. A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths. Math. Oper. Res., 36(4):743–753, 2011. doi:10.1287/moor.1110.0515.
[24] Volker Kaibel and Stefan Weltge. Lower bounds on the sizes of integer programs without additional variables. Math. Program., 154(1-2):407–425, 2015. doi:10.1007/s10107-014-0855-0.
[25] Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. Parameterized complexity of configuration integer programs. Oper. Res. Lett., 49(6):908–913, 2021. doi:10.1016/j.orl.2021.11.005.
[26] Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. High-multiplicity n-fold IP via configuration LP. Math. Program., 200(1):199–227, 2023. doi:10.1007/s10107-022-01882-9.
[27] Dusan Knop, Michal Pilipczuk, and Marcin Wrochna. Tight complexity lower bounds for integer linear programming with few constraints. ACM Trans. Comput. Theory, 12(3):19:1–19:19, 2020. doi:10.1145/3397484.
[28] Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, and Marek Sokolowski. Detecting points in integer cones of polytopes is double-exponentially hard. In 2024 Symposium on Simplicity in Algorithms, SOSA, pages 279–285. SIAM, 2024. doi:10.1137/1.9781611977936.25.
[29] Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki. Coverability in VASS revisited: Improving rackoff’s bounds to obtain conditional optimality. J. ACM, 72(5):33:1–33:27, 2025. doi:10.1145/3762178.
[30] Kenneth L. Manders and Leonard M. Adleman. Np-complete decision problems for quadratic polynomials. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3-5, 1976, Hershey, Pennsylvania, USA, pages 23–29. ACM, 1976. doi:10.1145/800113.803627.
[31] Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, volume 55 of LIPIcs, pages 28:1–28:15, 2016. doi:10.4230/LIPIcs.ICALP.2016.28.
[32] Garth P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I - convex underestimating problems. Math. Program., 10(1):147–175, 1976. doi:10.1007/BF01580665.
[33] S. Thomas McCormick, Scott R. Smallwood, and Frits C. R. Spieksma. A polynomial algorithm for multiprocessor scheduling with two job lengths. Math. Oper. Res., 26(1):31–49, 2001. doi:10.1287/moor.26.1.31.10590.
[34] Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res., 100:254–261, 2018. doi:10.1016/j.cor.2018.07.020.
[35] Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
[36] Craig A. Tovey. A simplified np-complete satisfiability problem. Discret. Appl. Math., 8(1):85–89, 1984. doi:10.1016/0166-218X(84)90081-7.

Appendix A Omitted Proofs

A.1 Proof of Claims 11–13

Claim 11 (✀). [Restated, see original statement.]

The constraints given in Equations C2–★ C5 ensure that $z_{\log n}$ contains exactly the block of $Z$ corresponding to variable $v_{i}$ , i.e., for $i\in[n]_{0}$ we get $z_{\log n}=C^{(i)}_{pos1}\cdot(\gamma^{m})^{0}+C^{(i)}_{pos2}\cdot(\gamma^{m})% ^{1}+C^{(i)}_{neg\vphantom{p2}}\cdot(\gamma^{m})^{2}$ . Additionally, the values of all introduced variables are unique for fixed $i$ and $Z$ .

Proof.

We show by induction over $j\in[\log(n)+1]_{0}$ , that after $j$ search steps, the variable $z_{j}$ equals the integer represented by a contiguous subsequence of $\frac{n}{2^{j}}$ blocks and that this subsequence contains the $i$ -th block.

Base Case: Assume $j=0$ . Then, by Equation C2 we have, $z_{0}=Z$ . As $Z$ contains all $\frac{n}{2^{j}}=n$ blocks, this also holds for the $i$ -th block. The Euclidean division of Equation C3, in combination with the bound of remainder $r_{0}$ , ensures that both, the quotient $q_{0}=\left\lfloor\frac{Z}{(\gamma^{m})^{3n/2}}\right\rfloor$ and the remainder $r_{0}$ are unique. Note, that $Z$ is now split into two integers $q_{0}$ and $r_{0}$ that represent two equal-sized subsequences.

Inductive Step: Let $j\in[\log(n)]_{0}$ and assume that $z_{j}$ equals the integer represented by a contiguous subsequence of $\frac{n}{2^{j}}$ blocks and that this subsequence contains the $i$ -th block. For the same reason as stated in the base case, the Euclidean division gives unique values for $q_{j}$ and $r_{j}$ . Equation ★ C5 now simulates a case distinction. Take the $(j+1)$ -th bit $x_{j+1}^{\texttt{bin}}$ of the binary representation of $i$ . If $x_{j+1}^{\texttt{bin}}=0$ we keep the lower half, i.e., we set $z_{j+1}=r_{j}$ . If $x_{j+1}^{\texttt{bin}}=1$ we keep the upper half, i.e., we set $z_{j+1}=q_{j}$ . In either case $z_{j+1}$ equals the concatenation of the blocks of the chosen half which contains exactly $\frac{n}{2^{j+1}}$ blocks as $n$ is a power of 2. Also, since $\boldsymbol{x}^{\texttt{bin}}$ is the binary representation of $i$ , the $i$ -th block remains in the selected half.

Finally, after $\log(n)$ steps, the subsequence consists of $\frac{n}{2^{\log(n)}}=1$ block which is the $i$ -th block, i.e., $z_{\log(n)}=C^{(i)}_{pos1}\cdot(\gamma^{m})^{0}+C^{(i)}_{pos2}\cdot(\gamma^{m}% )^{1}+C^{(i)}_{neg\vphantom{p2}}\cdot(\gamma^{m})^{2}$ . $\hfill\vartriangleleft$

Claim 12 (✀). [Restated, see original statement.]

The constraints given in Equations C2–☆ C8 ensure that the variables $c_{pos1},c_{pos2}$ and $c_{neg}$ match the corresponding values in the definition of $Z$ in Equation 2 for a given $i$ , i.e., $c_{pos1}=C^{(i)}_{pos1},c_{pos2}=C^{(i)}_{pos2}$ and $c_{neg}=C^{(i)}_{neg\vphantom{p2}}$ . Additionally, the values of all introduced variables are unique for fixed $i$ and $Z$ .

Proof.

With Claim 11, we have $z_{\log(n)}=C^{(i)}_{pos1}\cdot(\gamma^{m})^{0}+C^{(i)}_{pos2}\cdot(\gamma^{m}% )^{1}+C^{(i)}_{neg\vphantom{p2}}\cdot(\gamma^{m})^{2}$ . Equation C6 together with $c_{pos1}<\gamma^{m}$ ensures $c_{pos1}=C^{(i)}_{pos1}$ as the Euclidean division separates the quotient $q_{c}=\left\lfloor\frac{z_{\log(n)}}{\gamma^{m}}\right\rfloor=C^{(i)}_{pos2}% \cdot(\gamma^{m})^{0}+C^{(i)}_{neg\vphantom{p2}}\cdot(\gamma^{m})^{1}$ and the remainder $c_{pos1}=z_{\log(n)}\mod\gamma^{m}$ . Note that both values are unique for fixed $i$ and $Z$ .

Equation C7 together with $c_{pos2}<\gamma^{m}$ simulates another Euclidean division that now extracts the correct values for $c_{pos2}$ and $c_{neg}$ . More concretely, we obtain the unique values $c_{neg}=\left\lfloor\frac{q_{c}}{\gamma^{m}}\right\rfloor=C^{(i)}_{neg% \vphantom{p2}}$ and $c_{pos2}=q_{c}\mod\gamma^{m}=C^{(i)}_{pos2}$ . $\hfill\vartriangleleft$

Claim 13 (✀). [Restated, see original statement.]

For $i\in[n]_{0}$ , the constraints given in Equations C2–☆ C12 imply that

\displaystyle\begin{pmatrix}\alpha_{1}\vphantom{C^{(i)}_{pos1}}\\ \alpha_{2}\vphantom{\gamma^{i}}\\ \alpha_{3}\end{pmatrix}\in\left\{\begin{pmatrix}C^{(i)}_{pos1}\\ \gamma^{i}\\ 0\\ \end{pmatrix},\begin{pmatrix}C^{(i)}_{pos2}\\ \gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}C^{(i)}_{neg\vphantom{p2}}\\ 2\cdot\gamma^{i}\\ 0\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ \gamma^{i}\\ 1\end{pmatrix},\begin{pmatrix}0\vphantom{C^{(i)}_{pos1}}\\ 0\\ 1\end{pmatrix}\right\}.

All other introduced variables are binary (part of $\boldsymbol{\chi}$ ).

Proof.

Note that by [22], we have $\tilde{r}_{\log(n)}=\gamma^{i}$ for given $i\in[n]_{0}$ . We now make a case distinction over the value of $\alpha_{3}$ . Since it is binary, we consider the following two cases.

Case 1.

Assume $\alpha_{3}=1$ . Then the left-hand side of Equation C11 equals 0. This implies $\chi_{1}+\chi_{2}+\chi_{3}=0$ and therefore $\chi_{1}=\chi_{2}=\chi_{3}=0$ . With this, and Equation ★ C9, we get:

\displaystyle\alpha_{1}=c_{pos1}\cdot 0+c_{pos2}\cdot 0+c_{neg}\cdot 0=0

With Equation ★ C10, we get

\displaystyle\alpha_{2}=\tilde{r}_{\log(n)}\cdot\chi_{4}

Now, the inequality $\chi_{4}\leq\alpha_{3}$ allows $\chi_{4}\in\{0,1\}$ , thus:

\displaystyle\begin{pmatrix}\alpha_{1}\\ \alpha_{2}\\ \alpha_{3}\end{pmatrix}=\begin{cases}(0,\tilde{r}_{\log(n)},1)^{T}=(0,\gamma^{% i},1)^{T},&\text{if }\chi_{4}=1\\ (0,0,1)^{T}=(0,0,1)^{T},&\text{if }\chi_{4}=0\end{cases}

Case 2.

Assume $\alpha_{3}=0$ . Now, the left-hand side of Equation C11 equals 1. Therefore, exactly one of $\chi_{1},\chi_{2}$ , and $\chi_{3}$ equals 1 and the other two equal 0. The inequality $\chi_{4}\leq\alpha_{3}$ implies $\chi_{4}=0$ . With Equations ★ C9 and ★ C10, we get the following possibilities for $\alpha_{1}$ and $\alpha_{2}$ :

\displaystyle\begin{pmatrix}\alpha_{1}\vphantom{C^{(i)}_{pos1}}\\ \alpha_{2}\vphantom{C^{(i)}_{pos1}}\\ \alpha_{3}\vphantom{C^{(i)}_{pos1}}\end{pmatrix}=\begin{cases}(C^{(i)}_{pos1},% \tilde{r}_{\log(n)},0)^{T}=(C^{(i)}_{pos1},\gamma^{i},0)^{T},&\text{if }\chi_{% 1}=1\text{ and }\chi_{2}=\chi_{3}=0\\ (C^{(i)}_{pos2},\tilde{r}_{\log(n)},0)^{T}=(C^{(i)}_{pos2},\gamma^{i},0)^{T},&% \text{if }\chi_{2}=1\text{ and }\chi_{1}=\chi_{3}=0\\ (C^{(i)}_{neg\vphantom{p2}},2\cdot\tilde{r}_{\log(n)},0)^{T}=(C^{(i)}_{neg% \vphantom{p2}},2\cdot\gamma^{i},0)^{T},&\text{if }\chi_{3}=1\text{ and }\chi_{% 1}=\chi_{2}=0\end{cases}

As this case distinction is exhaustive, there are no other possibilities. This completes the proof. $\hfill\vartriangleleft$

Appendix B Omitted Constraints

In this section, we give the linearized constraints referred to in Theorem 10. The constraints can be obtained through a direct application of Lemma 6 to Equation ★ C5 and Equations ★ C9 and ★ C10.

B.1 Linearization of Constraints (★ $\rightarrow$ ☆)

B.1.1 Decoding Constraints (★ C5)

The linearization follows by applying Lemma 6. As an upper bound for each variable, we set $U^{\texttt{dc}}:=\gamma^{3nm}$ , since the maximum size of any variable is bounded by $Z$ , which in turn is bounded by $\gamma^{3nm}$ (see Lemma 9 for details):

\displaystyle\begin{array}[]{rll}z_{j+1}-q_{j}&\leq U^{\texttt{dc}}\cdot(1-x^{% \texttt{bin}}_{j+1})&\forall j\in[\log(n)]_{0}\\ z_{j+1}-q_{j}&\geq-U^{\texttt{dc}}\cdot(1-x^{\texttt{bin}}_{j+1})&\forall j\in% [\log(n)]_{0}\\ z_{j+1}-r_{j}&\leq U^{\texttt{dc}}\cdot x^{\texttt{bin}}_{j+1}&\forall j\in[% \log(n)]_{0}\\ z_{j+1}-r_{j}&\geq-U^{\texttt{dc}}\cdot x^{\texttt{bin}}_{j+1}&\forall j\in[% \log(n)]_{0}\end{array}

(☆C5)

B.1.2 Clause Constraints (★ C9), (★ C10)

The linearization follows by applying Lemma 6, where $U^{\texttt{cc}}$ is an upper bound for the involved variables. By construction, $\alpha_{1},c_{p1},c_{p2},c_{n}\leq\gamma^{m}$ and $\alpha_{2}\leq 2\cdot\gamma^{n}$ . Therefore, we set $U^{\texttt{cc}}\coloneqq\max(2\cdot\gamma^{n},\gamma^{m}-1)$ :

\displaystyle\begin{array}[]{rl}\alpha_{1}-c_{pos1}&\leq U^{\texttt{cc}}\cdot(% 1-\chi_{1})\\ \alpha_{1}-c_{pos1}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{1})\\ \alpha_{1}-c_{pos2}&\leq U^{\texttt{cc}}\cdot(1-\chi_{2})\\ \alpha_{1}-c_{pos2}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{2})\\ \alpha_{1}-c_{neg}&\leq U^{\texttt{cc}}\cdot(1-\chi_{3})\\ \alpha_{1}-c_{neg}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{3})\\ \alpha_{1}&\leq U^{\texttt{cc}}\cdot\left(\chi_{1}+\chi_{2}+\chi_{3}\right)% \end{array}

(☆C9)

\displaystyle\begin{array}[]{rl}\alpha_{2}-\tilde{r}_{\log(n)}&\leq U^{\texttt% {cc}}\cdot(1-\chi_{1})\\ \alpha_{2}-\tilde{r}_{\log(n)}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{1})\\ \alpha_{2}-\tilde{r}_{\log(n)}&\leq U^{\texttt{cc}}\cdot(1-\chi_{2})\\ \alpha_{2}-\tilde{r}_{\log(n)}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{2})\\ \alpha_{2}-2\cdot\tilde{r}_{\log(n)}&\leq U^{\texttt{cc}}\cdot(1-\chi_{3})\\ \alpha_{2}-2\cdot\tilde{r}_{\log(n)}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{3})\\ \alpha_{2}-\tilde{r}_{\log(n)}&\leq U^{\texttt{cc}}\cdot(1-\chi_{4})\\ \alpha_{2}-\tilde{r}_{\log(n)}&\geq-U^{\texttt{cc}}\cdot(1-\chi_{4})\\ \alpha_{2}&\leq U^{\texttt{cc}}\cdot\left(\chi_{1}+\chi_{2}+\chi_{3}+\chi_{4}% \right)\end{array}

(☆C10)

B.2 Construction of Equality Constraints

In this section, we introduce slack variables to turn the linear constraints of the prior section into equations. We start by stating the linear equality constraints equivalent to Equation ★ C1.

B.2.1 Variable Constraints

See [22] for details and proofs. Our notation differs slightly: we renamed some variables and, unlike [22], $x^{\texttt{bin}}_{1}$ is the most significant bit in $\boldsymbol{x}^{\texttt{bin}}$ .

\displaystyle\begin{array}[]{rll}\tilde{r}_{0}&=1\\ (\gamma^{2^{j+1}}+\gamma^{2^{j}})\tilde{y}_{j}-(\gamma^{2^{j}}+1)\tilde{r}_{j+% 1}+\tilde{s}_{1,j}&=\gamma^{2^{j}}&\forall j\in[\log(n)]_{0}\\ -\gamma^{2^{j}}\tilde{y}_{j}+\tilde{r}_{j+1}+\tilde{s}_{2,j}&=\gamma^{2^{j}}-1% &\forall j\in[\log(n)]_{0}\\ x^{\texttt{bin}}_{\log(n)-j}+\tilde{s}_{3,j}&=1&\forall j\in[\log(n)]_{0}\\ x^{\texttt{bin}}_{\log(n)-j}-\tilde{y}_{j}+\tilde{s}_{4,j}&=0&\forall j\in[% \log(n)]_{0}\\ \tilde{y}_{j}-(\gamma^{2^{j}}+1)x^{\texttt{bin}}_{\log(n)-j}+\tilde{s}_{5,j}&=% 0&\forall j\in[\log(n)]_{0}\\ (\gamma^{2^{j}}-1)\tilde{z}_{j}+\tilde{r}_{j}-\tilde{r}_{j+1}&=0&\forall j\in[% \log(n)]_{0}\\ \gamma^{2^{j}}x^{\texttt{bin}}_{\log(n)-j}-\tilde{z}_{j}+\tilde{r}_{j}+\tilde{% s}_{7,j}&=\gamma^{2^{j}}&\forall j\in[\log(n)]_{0}\\ -\gamma^{2^{j}}x^{\texttt{bin}}_{\log(n)-j}+\tilde{z}_{j}+\tilde{s}_{8,j}&=0&% \forall j\in[\log(n)]_{0}\\ \tilde{z}_{j}-\tilde{r}_{j}+\tilde{s}_{9,j}&=0&\forall j\in[\log(n)]_{0}\\ \tilde{r}_{\log(n)}-s_{9\log(n)}&=1&\\ \tilde{r}_{\log(n)}+s_{9\log(n)+1}&=\gamma^{n-1}&\end{array}

(C1)

The lower bound of each variable is 0. The largest upper bound of the variables is $\gamma^{O(n)}$ . Also, the absolute values of the coefficients and the right hand sides of these constraints are upper bounded by $\gamma^{O(n)}$ .

B.2.2 Decoding Constraints

The constraints in Equations ☆ C4, ☆C5, and ☆ C8 can be transformed into equality constraints through the introduction of slack variables $y^{\texttt{dc}}_{\ell,j}$ for all $\ell\in[8],j\in[\log(n)]_{0}$ .

$\displaystyle z_{0}$	$\displaystyle=Z$		(C2)
$\displaystyle z_{j}-q_{j}\cdot(\gamma^{m})^{3n/2^{j+1}}-r_{j}$	$\displaystyle=0$	$\displaystyle\forall j\in[\log(n)]_{0}$	(C3)
$\displaystyle r_{j}+y^{\texttt{dc}}_{1,j}$	$\displaystyle=(\gamma^{m})^{3n/2^{j+1}}-1$	$\displaystyle\forall j\in[\log(n)]_{0}$	(C4)

\displaystyle\begin{array}[]{rll}z_{j+1}-q_{j}+U^{\texttt{dc}}\cdot x^{\texttt% {bin}}_{j+1}+y^{\texttt{dc}}_{2,j}&=U^{\texttt{dc}}&\forall j\in[\log(n)]_{0}% \\ -z_{j+1}+q_{j}+U^{\texttt{dc}}\cdot x^{\texttt{bin}}_{j+1}+y^{\texttt{dc}}_{3,% j}&=U^{\texttt{dc}}&\forall j\in[\log(n)]_{0}\\ z_{j+1}-r_{j}-U^{\texttt{dc}}\cdot x^{\texttt{bin}}_{j+1}+y^{\texttt{dc}}_{4,j% }&=0&\forall j\in[\log(n)]_{0}\\ z_{j+1}-r_{j}+U^{\texttt{dc}}\cdot x^{\texttt{bin}}_{j+1}-y^{\texttt{dc}}_{5,j% }&=0&\forall j\in[\log(n)]_{0}\end{array}

(C5)

	$\displaystyle z_{\log(n)}$	$\displaystyle=q_{c}\cdot\gamma^{m}+c_{pos1}$		(C6)
	$\displaystyle q_{c}$	$\displaystyle=c_{neg}\cdot\gamma^{m}+c_{pos2}$		(C7)

\displaystyle\begin{array}[]{rl}c_{pos1}+y^{\texttt{dc}}_{6}&=\gamma^{m}-1\\ c_{pos2}+y^{\texttt{dc}}_{7}&=\gamma^{m}-1\\ c_{neg}+y^{\texttt{dc}}_{8}&=\gamma^{m}-1\end{array}

(C8)

Again, each variable is lower bounded by 0. The upper bounds can be set as follows:

$\displaystyle z_{j}$	$\displaystyle\leq(\gamma^{m})^{\frac{3n}{2^{j}}}$	$\displaystyle\forall j\in[\log(n)]_{0}$
$\displaystyle q_{j},r_{j}$	$\displaystyle\leq(\gamma^{m})^{3n/2^{j+1}}-1$	$\displaystyle\forall j\in[\log(n)]_{0}$
$\displaystyle q_{c}$	$\displaystyle\leq(\gamma^{m})^{2}$
$\displaystyle c_{pos1},c_{pos2},c_{neg}$	$\displaystyle\leq(\gamma^{m})-1$
$\displaystyle y^{\texttt{dc}}_{1,j}$	$\displaystyle\leq(\gamma^{m})^{3n/2^{j+1}}-1$	$\displaystyle\forall j\in[\log(n)]_{0}$
$\displaystyle y^{\texttt{dc}}_{\ell,j}$	$\displaystyle\leq 2(\gamma^{m})^{3n}$	$\displaystyle\forall\ell\in\{2,\dots,5\},\forall j\in[\log(n)]_{0}$
$\displaystyle y^{\texttt{dc}}_{\ell}$	$\displaystyle\leq(\gamma^{m})-1$	$\displaystyle\forall\ell\in\{6,7,8\}$

Both, the largest absolute value of the coefficients and the right-hand side is $U^{\texttt{dc}}=\gamma^{3nm}$ (Equation C5).

B.2.3 Clause Constraints

Finally, the constraints in Equations ☆C9–☆ C12 can be transformed into equality constrains through the introduction of slack variables $y^{\texttt{cc}}_{\ell}$ for each $\ell\in[15]$ .

\displaystyle\begin{array}[]{rl}\alpha_{1}-c_{pos1}+U^{\texttt{cc}}\cdot\chi_{% 1}+y^{\texttt{cc}}_{1}&=U^{\texttt{cc}}\\ -\alpha_{1}+c_{pos1}+U^{\texttt{cc}}\cdot\chi_{1}+y^{\texttt{cc}}_{2}&=U^{% \texttt{cc}}\\ \alpha_{1}-c_{pos2}+U^{\texttt{cc}}\cdot\chi_{2}+y^{\texttt{cc}}_{3}&=U^{% \texttt{cc}}\\ -\alpha_{1}+c_{pos2}+U^{\texttt{cc}}\cdot\chi_{2}+y^{\texttt{cc}}_{4}&=U^{% \texttt{cc}}\\ \ \alpha_{1}-c_{neg}+U^{\texttt{cc}}\cdot\chi_{3}+y^{\texttt{cc}}_{5}&=U^{% \texttt{cc}}\\ -\alpha_{1}+c_{neg}+U^{\texttt{cc}}\cdot\chi_{3}+y^{\texttt{cc}}_{6}&=U^{% \texttt{cc}}\end{array}

(C9)

\displaystyle\begin{array}[]{rl}\alpha_{2}-\tilde{r}_{\log(n)}+U^{\texttt{cc}}% \cdot\chi_{1}+y^{\texttt{cc}}_{7}&=U^{\texttt{cc}}\\ -\alpha_{2}+\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{1}+y^{\texttt{cc}}_{% 8}&=U^{\texttt{cc}}\\ \alpha_{2}-\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{2}+y^{\texttt{cc}}_{9% }&=U^{\texttt{cc}}\\ -\alpha_{2}+\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{2}+y^{\texttt{cc}}_{% 10}&=U^{\texttt{cc}}\\ \alpha_{2}-2\cdot\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{3}+y^{\texttt{% cc}}_{11}&=U^{\texttt{cc}}\\ -\alpha_{2}+2\cdot\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{3}+y^{\texttt{% cc}}_{12}&=U^{\texttt{cc}}\\ \alpha_{2}-\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{4}+y^{\texttt{cc}}_{1% 3}&=U^{\texttt{cc}}\\ -\alpha_{2}+\tilde{r}_{\log(n)}+U^{\texttt{cc}}\cdot\chi_{4}+y^{\texttt{cc}}_{% 14}&=U^{\texttt{cc}}\end{array}

(C10)

	$\displaystyle\chi_{1}+\chi_{2}+\chi_{3}+\alpha_{3}$	$\displaystyle=1$		(C11)
	$\displaystyle\chi_{4}-\alpha_{3}+y^{\texttt{cc}}_{15}$	$\displaystyle=0$		(C12)

As usual, the lower bound of the variables is 0. We can set the upper bounds to:

$\displaystyle\alpha_{1}$	$\displaystyle\leq\gamma^{m}$
$\displaystyle\alpha_{2}$	$\displaystyle\leq 2\gamma^{n}$
$\displaystyle\alpha_{3}$	$\displaystyle\leq 1$
$\displaystyle\chi_{\ell}$	$\displaystyle\leq 1$	$\displaystyle\forall\ell\in[4]$
$\displaystyle y^{\texttt{cc}}_{\ell}$	$\displaystyle\leq 2U^{\texttt{cc}}=4\gamma^{n}$	$\displaystyle\forall\ell\in[14]$
$\displaystyle y^{\texttt{cc}}_{15}$	$\displaystyle\leq 1$

Here, the largest absolute value of the coefficients and the right-hand side is $U^{\texttt{cc}}=\max(2\cdot\gamma^{n},\gamma^{m}-1)$ (Equations C9 and C10).

[bib.bib1] [1] Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, and Robert Weismantel. Forall-exist statements in pseudopolynomial time. In SODA, pages 2225–2233. SIAM, 2025. doi:10.1137/1.9781611978322.73.

[bib.bib2] [2] Piotr Berman, Marek Karpinski, and Alexander D. Scott. Computational complexity of some restricted instances of 3-sat. Discret. Appl. Math., 155(5):649–653, 2007. doi:10.1016/j.dam.2006.07.009.

[bib.bib3] [3] William J. Cook, Mark Hartmann, Ravi Kannan, and Colin McDiarmid. On integer points in polyhedra. Comb., 12(1):27–37, 1992. doi:10.1007/BF01191202.

[bib.bib4] [4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib5] [5] Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM J. Comput., 45(1):67–83, 2016. doi:10.1137/130947076.

[bib.bib6] [6] Friedrich Eisenbrand and Gennady Shmonin. Carathéodory bounds for integer cones. Oper. Res. Lett., 34(5):564–568, 2006. doi:10.1016/j.orl.2005.09.008.

[bib.bib7] [7] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms, 15(1):9:1–9:27, 2019. doi:10.1145/3280824.

[bib.bib8] [8] Robert Fortet. Applications de l’algebre de boole en recherche opérationelle. Revue Française de Recherche Opérationelle, 4(14):17–26, 1960.

[bib.bib9] [9] Paul C Gilmore and Ralph E Gomory. A linear programming approach to the cutting-stock problem. Operations research, 9(6):849–859, 1961. doi:10.1287/opre.9.6.849.

[bib.bib10] [10] Fred W. Glover and Eugene Woolsey. Technical note - converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res., 22(1):180–182, 1974. doi:10.1287/opre.22.1.180.

[bib.bib11] [11] Michel X. Goemans and Thomas Rothvoss. Polynomiality for bin packing with a constant number of item types. J. ACM, 67(6):38:1–38:21, 2020. doi:10.1145/3421750.

[bib.bib12] [12] Mark E. Hartmann. Cutting planes and the complexity of the integer hull. Technical report, Cornell University, September 1988. URL: https://hdl.handle.net/1813/8702.

[bib.bib13] [13] David Harvey and Joris van der Hoeven. Integer multiplication in time o(nlog n). Annals of Mathematics, 193(2):563–617, 2021. doi:10.4007/annals.2021.193.2.4.

[bib.bib14] [14] Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, and Asaf Levin. Tight lower bounds for block-structured integer programs. Math. Program., 2025. doi:10.1007/s10107-025-02296-z.

[bib.bib15] [15] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In 39th Annual Symposium on Foundations of Computer Science, FOCS, pages 653–663. IEEE Computer Society, 1998. doi:10.1109/SFCS.1998.743516.

[bib.bib16] [16] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.

[bib.bib17] [17] Klaus Jansen and Kim-Manuel Klein. About the structure of the integer cone and its application to bin packing. Math. Oper. Res., 45(4):1498–1511, 2020. doi:10.1287/moor.2019.1040.

[bib.bib18] [18] Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota. The double exponential runtime is tight for 2-stage stochastic ilps. Math. Program., 197(2):1145–1172, 2023. doi:10.1007/s10107-022-01837-0.

[bib.bib19] [19] Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci., 79(1):39–49, 2013. doi:10.1016/J.JCSS.2012.04.004.

[bib.bib20] [20] Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discret. Math., 30(1):343–366, 2016. doi:10.1137/140952636.

[bib.bib21] [21] Klaus Jansen and Haiko Müller. The minimum broadcast time problem for several processor networks. Theor. Comput. Sci., 147(1&2):69–85, 1995. doi:10.1016/0304-3975(94)00230-G.

[bib.bib22] [22] Klaus Jansen, Lis Pirotton, and Malte Tutas. The support of bin packing is exponential. In 33rd Annual European Symposium on Algorithms, ESA 2025, LIPIcs, pages 48:1–48:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.48.

[bib.bib23] [23] Klaus Jansen and Roberto Solis-Oba. A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths. Math. Oper. Res., 36(4):743–753, 2011. doi:10.1287/moor.1110.0515.

[bib.bib24] [24] Volker Kaibel and Stefan Weltge. Lower bounds on the sizes of integer programs without additional variables. Math. Program., 154(1-2):407–425, 2015. doi:10.1007/s10107-014-0855-0.

[bib.bib25] [25] Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. Parameterized complexity of configuration integer programs. Oper. Res. Lett., 49(6):908–913, 2021. doi:10.1016/j.orl.2021.11.005.

[bib.bib26] [26] Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. High-multiplicity n-fold IP via configuration LP. Math. Program., 200(1):199–227, 2023. doi:10.1007/s10107-022-01882-9.

[bib.bib27] [27] Dusan Knop, Michal Pilipczuk, and Marcin Wrochna. Tight complexity lower bounds for integer linear programming with few constraints. ACM Trans. Comput. Theory, 12(3):19:1–19:19, 2020. doi:10.1145/3397484.

[bib.bib28] [28] Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, and Marek Sokolowski. Detecting points in integer cones of polytopes is double-exponentially hard. In 2024 Symposium on Simplicity in Algorithms, SOSA, pages 279–285. SIAM, 2024. doi:10.1137/1.9781611977936.25.

[bib.bib29] [29] Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki. Coverability in VASS revisited: Improving rackoff’s bounds to obtain conditional optimality. J. ACM, 72(5):33:1–33:27, 2025. doi:10.1145/3762178.

[bib.bib30] [30] Kenneth L. Manders and Leonard M. Adleman. Np-complete decision problems for quadratic polynomials. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3-5, 1976, Hershey, Pennsylvania, USA, pages 23–29. ACM, 1976. doi:10.1145/800113.803627.

[bib.bib31] [31] Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, volume 55 of LIPIcs, pages 28:1–28:15, 2016. doi:10.4230/LIPIcs.ICALP.2016.28.

[bib.bib32] [32] Garth P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I - convex underestimating problems. Math. Program., 10(1):147–175, 1976. doi:10.1007/BF01580665.

[bib.bib33] [33] S. Thomas McCormick, Scott R. Smallwood, and Frits C. R. Spieksma. A polynomial algorithm for multiprocessor scheduling with two job lengths. Math. Oper. Res., 26(1):31–49, 2001. doi:10.1287/moor.26.1.31.10590.

[bib.bib34] [34] Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res., 100:254–261, 2018. doi:10.1016/j.cor.2018.07.020.

[bib.bib35] [35] Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.

[bib.bib36] [36] Craig A. Tovey. A simplified np-complete satisfiability problem. Discret. Appl. Math., 8(1):85–89, 1984. doi:10.1016/0166-218X(84)90081-7.

A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (Bin Packing).

Definition 2 (ETH, [15]).

Our Contribution

Theorem 3.

2 Preliminaries

Definition 4 (3-SAT).

Lemma 5 (✀, Well-Structured 3-SAT; Extension of [36]).

Proof.

Lemma 6 (✀).

Proof.

Lemma 7 ([22]).

Proof Sketch.

Lemma 8 (✀, [22]).

Proof Sketch.

3 Reduction from 3-SAT to Bin Packing

Lemma 9.

Proof.

3.1 Construction of the ILP

Theorem 10.

Claim 11 (✀).

Claim 12 (✀).

Claim 13 (✀).

3.2 Constructing the Bin Packing Instance

Lemma 14 (✀).

Claim 15.

Proof.

Lemma 16.

Proof.

3.3 Putting It All Together

Theorem 3. [Restated, see original statement.]

Proof.

4 Conclusion

References

Appendix A Omitted Proofs

A.1 Proof of Claims 11–13

Claim 11 (✀). [Restated, see original statement.]

Proof.

Claim 12 (✀). [Restated, see original statement.]

Proof.

Claim 13 (✀). [Restated, see original statement.]

Proof.

Case 1.

Case 2.

Appendix B Omitted Constraints

B.1 Linearization of Constraints (★→ ☆)

B.1.1 Decoding Constraints (★ C5)

B.1.2 Clause Constraints (★ C9), (★ C10)

B.2 Construction of Equality Constraints

B.2.1 Variable Constraints

B.2.2 Decoding Constraints

B.2.3 Clause Constraints

B.1 Linearization of Constraints (★ $\rightarrow$ ☆)