Какие задачи в вычислительной геометрии или теории графов считаются

Это задание является последующим вопросом к предыдущему посту Робина Котари о результатах определения полиномиального времени .

В частности, я заинтересован в том, чтобы увидеть некоторые доказательства твердости для задач, которые, как считается, имеют примерно нижних границ, и я говорю грубо, чтобы учесть слегка субкубические улучшения, играя с размером слова (например, для 3SUM: Бараб и др. [Через Спрингера] ). Я был бы рад сохранить проблемы в модели дерева решений, если это упростит ответы.$\Omega(n^3)$

От поста Робина, я узнал о Джеффа Эриксона бумаги , которая дает нижняя граница для 5SUM (точнее, он показывает , что к -sum работает в П ( п ⌈ к / 2 ⌉ ) времени в целом).$\Omega(n^3)$$k$$\Omega (n^{\lceil k/2 \rceil})$

Существуют ли статьи или другие ссылки, использующие такие редукции для предположения кубических нижних оценок для задач вычислительной геометрии или теории графов?

Я думаю, что вы ищете статью « Субкубические эквивалентности между задачами пути, матрицы и треугольника » В. Васильевской и Р. Уильямса. В его аннотации содержится список следующих задач на графиках:

• Проблема кратчайших путей для всех пар на весовых орграфах (APSP).
• Обнаружение, имеет ли взвешенный граф треугольник с отрицательным общим весом ребра.
• $n^{2.99}$
• Проблема путей замещения на весовых орграфах.
• Нахождение второго кратчайшего простого пути между двумя узлами во взвешенном орграфе.

Согласно реферату, статья о следующем:

$O(n^3)$

Затем можно использовать сокращения к этой проблеме в качестве отправной точки для доказательства нижних оценок. См., Например, раздел 5 следующей статьи: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . Также раздел 4 и 5 в следующем документе: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Я уверен, что есть и другие примеры - это просто статьи, над которыми я работал, и они помнят, что они используют такую ​​аргументацию.

$\Re^5$$\Re^5$$\Omega(n^5)$