Lower Bounds Under Strong Complexity Assumptions

Praca poświęcna jest ograniczeniom dolnym na czasy działania przy silnych założeniach złożonościowych. Dowodzimy, że przy założeniu Exponential Time Hypothesis nie istnieje algorytm działający w czasie• 2^o(n log n) (razy czynnik wielomianowy względem rozmiaru instancji w bitach) dla problemu Channel Assignment,• 2^o(n sqrt(log n)) dla problemu Subgraph Isomorphism,• 2^o(n^3/2) dla problemu Rainbow k-Coloring (dla żadnego k ­≥ 2),• f(b) · 2^(o(log b)·n) dla problemu (a:b)-coloring (dla żadnego obliczalnego f(b)),• O*(2^o(d log d)) dla problemu Minimax Approval Voting.To w szczególności wyklucza istnienie algorytmów rozwiązujących te problemy w czasie O*(c^n) (lub O*(c^d) w przypadku problemu Minimax Approval Voting) dla dowolnej stałej c. Ponadto w przypadku problemów Channel Assignment, (a:b)-coloring oraz Minimax Approval Voting nasze ograniczenia dolne są dokładne, czyli pokazują, że obecnie znane algorytmy są optymalne (przy założeniu ETH).Podajemy również ograniczenie dolne innego rodzaju. Pokazujemy, że poprawienie najlepszego znanego algorytmu dla problemu 4-OPT Detection (problemu związanego z problemem komiwojażera), implikowałoby poprawę algorytmu dla problemu All Pairs Shortest Paths.

This work is devoted to lower bounds on running time under strong complexity assumptions. We prove that under the Exponential Time Hypothesis there is no algorithm working in time• 2^o(n log n) (times a polynomial in the bit size) for Channel Assignment,• 2^o(n sqrt(log n)) for Subgraph Isomorphism,• 2^o(n^3/2) for Rainbow k-Coloring (for any k ≥ 2),• f(b) · 2^(o(log b)·n) for (a:b)-coloring (for any computable f(b)),• O*(2^o(d log d)) for Minimax Approval Voting.This in particular exclude the existence of algorithms solving these problems in time O*(c^n) (or O*(c^d) in the case of Minimax Approval Voting) for any constant c. Moreover in the cases of Channel Assignment, (a:b)-coloring and Minimax Approval Voting our lower bounds are tight, showing that currently known algorithms are optimal (unless ETH fails). We also give a lower bound of a different flavor. We show that improving over the best known algorithm for 4-OPT Detection (a problem related to Traveling Salesman Problem), would imply an improvement for All Pairs Shortest Paths.