Характеристика задач, для которых существуют алгоритмы сублинейного времени

16

Мне было интересно, можно ли охарактеризовать проблемы, для которых существуют алгоритмы сублинейного времени (в размере входных данных) как обладающие определенными свойствами. Это включает в себя сублинейное время (например, тестирование свойств, альтернативное понятие аппроксимации для задач решения), сублинейное пространство (например, алгоритмы создания эскизов / потоковой передачи, в которых машина Тьюринга имеет ленту только для чтения, сублинейное рабочее пространство и выходные данные только для записи лента) и сублинейные измерения (например, редкое восстановление / измерение сжатия). В частности, меня интересует такая характеристика как в рамках алгоритмов тестирования свойств, так и в классической модели рандомизированных и аппроксимационных алгоритмов.

Например, проблемы, для которых существует решение динамического программирования, демонстрируют оптимальную подструктуру и перекрывающиеся подзадачи; те, для которых существует жадное решение, обладают оптимальной субструктурой и структурой матроида. И так далее. Любая ссылка на эту тему приветствуется.

За исключением нескольких проблем, которые допускают детерминированный сублинейный алгоритм, почти все сублинейные алгоритмы, которые я видел, являются рандомизированными. Есть ли какой-то конкретный класс сложности, связанный с проблемами, допускающими сублинейные алгоритмы времени? Если да, включен ли этот класс в BPP или PCP?

Массимо Кафаро
источник
5
сублинейное время в какой модели?
Каве
1
Алгоритмы тестирования свойств находятся в общих рамках того, что вы хотите, но сначала нужно ответить на вопрос Каве.
Суреш Венкат
Я отредактировал свой вопрос, добавив запрашиваемую информацию.
Массимо Кафаро
Преобразование Фурье вектора может быть вычислено за сублинейное время, когда оно (почти) разрежено в частотной области. Таким образом, собственность здесь является редкостью. Посмотрите, например, «Простой и практичный алгоритм редкого преобразования Фурье» Хайтама Хассании, Петра Индика, Дины Катаби и Эрика Прайса nms.lcs.mit.edu/~dina/pub/soda12.pdf и ссылки в нем. k
Димитрис

Ответы:

13

Для постоянной задачи тестирования свойств графа известна интересная характеристика. Свойство графа является функцией от всех графов , и график , свойство Р является проверяемым , если есть рандомизированный алгоритм , что для всех х > 0 и всех графов G :{0,1}PAε>0G

  • читает только g ( ε ) ребер G для некоторой функции gA(G)g(ε)Gg
  • Если , то A ( G ) выходы `` Да '' с высокой степенью вероятности (скажем, по крайней мере , 2 / 3 )P(G)=1A(G)2/3
  • Если по крайней мере ребер G нужно добавить или удалить, чтобы получить G такой, что P ( G ) = 1 (то есть G является ε- дальним от свойства ), то A ( G ) выдает `` нет «» с вероятностью по крайней мере , 2 / 3εn2GGP(G)=1GεA(G)2/3

То есть, может различать между графиками , которые имеют Р и графики , которые имеют высокое редактировать расстояние от графов , имеющих P .APPАлон, Фишер, Ньюман и Шапира доказали, что свойство тестируется таким образом тогда и только тогда, когда свойство можно «свести» к свойству проверки, имеет ли граф ε -регулярное разбиение (в смысле Семереди). , Это показывает, что в некотором смысле регулярность тестирования является «полной» для тестирования. (Существует также версия тестируемости с односторонней ошибкой, см. Ссылку.)Pε

Райан Уильямс
источник
5

В области сублинейного пространства не существует явного класса задач, допускающих решение сублинейного пространства, но есть большие классы задач (оценка момента частоты, уменьшение размерности и т. Д.), Где можно показать существование небольшого «эскиза», и это приводит к эффективным алгоритмам.

Но и в этом пространстве все алгоритмы рандомизированы, и существуют сильные детерминированные нижние границы, в основном основанные на сложности коммуникации.

Суреш Венкат
источник