Есть ансамбль практических задач, которые мы умеем решать за полиномиальное время. Однако, почти везде наивный алгоритм является наиболее быстрым для этих задач и существенное
улучшение этих алгоритмов открытая задача. Есть три популярные гипотезы, которые позволяют доказывать нижние оценки (в предположении трудности классических задач) на время работы алгоритмов: SETH, APSP не решается за субкубическое время, 3SUM не решается за субквадтратичное время. Планируется рассказать о различных задачах на графах и что они не легче чем APSP. Например, почему найти все треугольники отрицательного веса в графе не легче чем посчитать все кратчайшие расстояния между парами вершин. В некоторых задачах даже поиск приближенного решения с константной ошибкой не легче поиска точного решения и причины этого мы тоже постараемся узнать.