Fine-Grained Complexity - Hardness in P - Max Planck Society

[Pages:54]Fine-Grained Complexity Hardness in P

Lecture 1: SETH and OV

Karl Bringmann

Machine Model

Random Access Machine (RAM):

CPU

? memory of ! 1 cells

? can perform all reasonable operations on two cells in ! 1 time (arithmetic + logical operations...)

? can read/write any cell in ! 1 time

storage:

101 011 001 111 ... 100 101 111

cell / word consisting of (log () bits

can recognize palindromes in time !(()

the details do not matter!

Reminder: SETH and OV

Problem !-SAT: Given formula in '-CNF with 1 variables, is it satisfiable?

2, ?25 26 25 ?26 28 (?2, 29 28)

Strong Exponential Time Hypothesis: [Impagliazzo,Paturi'01] # > 0 ': '-SAT has no )(2 ,-. /)-time algorithm

Problem Orthogonal Vectors: Given sets @, B {0,1}G of size 1, are any H @, J B orthogonal? (L HL JL = 0)

OV-Hypothesis: (moderate dimension) # > 0: OV has no )(15-. poly(?))-time algorithm

LD-OV-Hypothesis: (low dimension) # > 0 O > 0: OV in ? = O log 1 has no )(15-.)-time algorithm

SETH

[Williams'05]

LD-OVH

OVH

Reminder: Fine-Grained Reductions

transfer hardness of one problem to another one by reductions

problem ( instance '

size $ ' is a `yes'-instance

reduction

)($) time

()

problem ! instance &

size "($) & is a `yes'-instance

*($) algorithm for + implies a ) $ + *(" $ ) algorithm for if - has no ) $ + *(" $ ) algorithm then + has no *($) algorithm

Reminder: Fine-Grained Reductions

A fine-grained reduction from (", 1) to (#, 1') is an algorithm ! for " with oracle access to # s.t.:

problem , instance *

reduction

problem $

instance *1 size ')

... ...

size ' Properties:

total time %(')

instance *. size '-

for any instance *, algorithm !(*) correctly solves problem " on *

! runs in time %(') = 0(1('))23) for some 4 > 0

for any 7 > 0 there is a 8 > 0 s.t. :-;) 1(':))2= 1('))2?

Landscape of Polytime Problems 3SUM-hard

SETH SAT 2(

[Patrascu, Williams'10]

[Williams'05]

k-DomSet !$

OV !"

[B'14]

Frechet !"

[V-Williams,Roditty'13]

SETH-hard

[Abboud,B,Hermelin, Shabtay'17+]

SubsetSum !+&

[Backurs,Indyk'15]

Edit Distance !"

[B,K?nnemann'15,Abboud, Backurs,V-Williams'15]

3SUM !"

X+Y !"

[Gajentaan,Overmars'95]

GeomBase !"

Colinear !"

Separator !"

PlanarMotion Planning !"

Diameter !"

Dynamic Time Warping !"

APSP-hard

[B,K?nnemann'15, Abboud,Backurs, V-Williams'15]

LCS !"

[B,K?nnemann'15]

Longest Palindromic Subsequence !"

[Impagliazzo]

NFA-Acceptance !"

[Backurs,Indyk'16]

RegExp Matching !"

APSP !#

[Backurs,Dikkala, Tzamos'16]

[V-Williams, Williams'10]

Radius !#

Maximum Submatrix !#

Metricity !#

[B,Gawrychowski, Mozes,Weimann'18]

Betweenness Centrality !#

Tree Edit

Survey: On some fine-grained questions in

Distance !#

algorithms and complexity, V. Vassilevska Williams

NegTriangle !#

I. Easy Example II. Longest Common Subsequence III. Hardness of Approximation IV. Further Topics V. Summary

Landscape of Polytime Problems 3SUM-hard

SETH SAT 2(

[Patrascu, Williams'10]

[Williams'05]

k-DomSet !$

OV !"

[B'14]

Frechet !"

[V-Williams,Roditty'13]

SETH-hard

[Abboud,B,Hermelin, Shabtay'17+]

SubsetSum !+&

[Backurs,Indyk'15]

Edit Distance !"

[B,K?nnemann'15,Abboud, Backurs,V-Williams'15]

3SUM !"

X+Y !"

[Gajentaan,Overmars'95]

GeomBase !"

Colinear !"

Separator !"

PlanarMotion Planning !"

Diameter !"

Dynamic Time Warping !"

APSP-hard

[B,K?nnemann'15, Abboud,Backurs, V-Williams'15]

LCS !"

[B,K?nnemann'15]

Longest Palindromic Subsequence !"

[Impagliazzo]

NFA-Acceptance !"

[Backurs,Indyk'16]

RegExp Matching !"

APSP !#

[Backurs,Dikkala, Tzamos'16]

[V-Williams, Williams'10]

Radius !#

Maximum Submatrix !#

Metricity !#

[B,Gawrychowski, Mozes,Weimann'18]

Betweenness Centrality !#

Tree Edit Distance !#

NegTriangle !#

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download