The double exponential runtime is tight for 2-stage stochastic ILPs
Klaus Jansen, Kim-Manuel Klein, Alexandra Lassota · Mathematical Programming · 2022
Abstract We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form $$\min \{c^T x \mid {\mathcal {A}} x = b, \ell \le x \le u, x \in {\mathbb {Z}}^{r + ns} \}$$ min { c T x ∣ A x = b , ℓ ≤ x ≤ u , x ∈ Z r + n s } where the constraint matrix $${\mathcal {A}} \in {\mathbb {Z}}^{nt \times r +ns}$$ A ∈ Z n t × r + n s consists of n matrices $$A_i \in {\mathbb {Z}}^{t \times r}$$ A i ∈ Z t × r on the vertical line and n matrices $$B_i \in {\mathbb {Z}}^{t \times s}$$ B i ∈ Z t × s on the diagonal line aside. We show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number $$z \le \gamma $$ z ≤ γ satisfying $$z^2 \equiv \alpha \bmod \beta $$ z 2 ≡ α mod β for given $$\alpha , \beta , \gamma \in {\mathbb {Z}}$$ α , β , γ ∈ Z . This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of $$\beta $$ β admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Using this new hardness result for the $$\textsc {Quadratic Congruences}$$ Q U A D R A T I C C O N G R U E N C E S problem, we prove a lower bound of $$2^{2^{\delta (s+t)}} |I|^{O(1)}$$ 2 2 δ ( s + t ) | I | O ( 1 ) for some $$\delta > 0$$ δ > 0