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

12

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

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

От поста Робина, я узнал о Джеффа Эриксона бумаги , которая дает нижняя граница для 5SUM (точнее, он показывает , что к -sum работает в П ( п к / 2 ) времени в целом).Ω(n3)kΩ(nk/2)

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

Боб Фрейзер
источник
Оба эти ответа были полезны для меня, спасибо! Кроме того, указатель Джеффа на статью Тимоти был высоко оценен, это очень хороший результат.
Боб Фрейзер,

Ответы:

13

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

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

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

O(n3)

Александр бондаренко
источник
6
Но посмотрите также алгоритм субкубического APSP Тимоти Чана, который НЕ играет в битовые игры: springerlink.com/content/px2741688g4p4l18
Джефф
9

Затем можно использовать сокращения к этой проблеме в качестве отправной точки для доказательства нижних оценок. См., Например, раздел 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 . Я уверен, что есть и другие примеры - это просто статьи, над которыми я работал, и они помнят, что они используют такую ​​аргументацию.

55Ω(n5)

Сариэль Хар-Пелед
источник