Fine-Grained Completeness for Optimization in P

We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime.
Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the k-XOR problem. Specifically, we define MaxSP as the class of problems definable as max$_{x₁,… ,x_k}$ #{$(y₁,… ,y_𝓁)$ : ϕ$(x₁,… ,x_k, y₁,… ,y_𝓁)$}, where ϕ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On m-sized structures, we can solve each such problem in time $O(m^{k+𝓁-1})$. Our results are:
- We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under deterministic fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+𝓁-1})$ for all problems in MaxSP/MinSP by a polynomial factor. ... mehr
- This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic c-approximation would give a $(c+ε)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+𝓁-1-δ})$, where $ε > 0$ can be chosen arbitrarily small. Combining our completeness with (Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is equivalent to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+𝓁-1})$ time.
- By fine-tuning our reductions, we obtain mild algorithmic improvements for solving and approximating all problems in MaxSP and MinSP, using the fastest known algorithms for Maximum/Minimum Inner Product.