# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Fine-Grained Completeness for Optimization in P

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2107.01721.pdf

(Preprint), 769KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.

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.