Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Fine-Grained Completeness for Optimization in P


Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Cassis,  Alejandro
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Fischer,  Nick
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 769KB

Supplementary Material (public)
There is no public supplementary material available

Bringmann, K., Cassis, A., Fischer, N., & Künnemann, M. (2021). Fine-Grained Completeness for Optimization in P. Retrieved from https://arxiv.org/abs/2107.01721.

Cite as: https://hdl.handle.net/21.11116/0000-0008-E26A-2
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_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) :
\phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ 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+\ell-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+\ell-1})$ for *all* problems in MaxSP/MinSP by
a polynomial factor.
- 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+\varepsilon)$-approximation for all MaxSP/MinSP problems in
time $O(m^{k+\ell-1-\delta})$, where $\varepsilon > 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+\ell-1})$ time.