Мне было интересно, можно ли охарактеризовать проблемы, для которых существуют алгоритмы сублинейного времени (в размере входных данных) как обладающие определенными свойствами. Это включает в себя сублинейное время (например, тестирование свойств, альтернативное понятие аппроксимации для задач решения), сублинейное пространство (например, алгоритмы создания эскизов / потоковой передачи, в которых машина Тьюринга имеет ленту только для чтения, сублинейное рабочее пространство и выходные данные только для записи лента) и сублинейные измерения (например, редкое восстановление / измерение сжатия). В частности, меня интересует такая характеристика как в рамках алгоритмов тестирования свойств, так и в классической модели рандомизированных и аппроксимационных алгоритмов.
Например, проблемы, для которых существует решение динамического программирования, демонстрируют оптимальную подструктуру и перекрывающиеся подзадачи; те, для которых существует жадное решение, обладают оптимальной субструктурой и структурой матроида. И так далее. Любая ссылка на эту тему приветствуется.
За исключением нескольких проблем, которые допускают детерминированный сублинейный алгоритм, почти все сублинейные алгоритмы, которые я видел, являются рандомизированными. Есть ли какой-то конкретный класс сложности, связанный с проблемами, допускающими сублинейные алгоритмы времени? Если да, включен ли этот класс в BPP или PCP?
Ответы:
Для постоянной задачи тестирования свойств графа известна интересная характеристика. Свойство графа является функцией от всех графов , и график , свойство Р является проверяемым , если есть рандомизированный алгоритм , что для всех х > 0 и всех графов G :{0,1} P A ε>0 G
То есть, может различать между графиками , которые имеют Р и графики , которые имеют высокое редактировать расстояние от графов , имеющих P .A P P Алон, Фишер, Ньюман и Шапира доказали, что свойство тестируется таким образом тогда и только тогда, когда свойство можно «свести» к свойству проверки, имеет ли граф ε -регулярное разбиение (в смысле Семереди). , Это показывает, что в некотором смысле регулярность тестирования является «полной» для тестирования. (Существует также версия тестируемости с односторонней ошибкой, см. Ссылку.)P ε
источник
В области сублинейного пространства не существует явного класса задач, допускающих решение сублинейного пространства, но есть большие классы задач (оценка момента частоты, уменьшение размерности и т. Д.), Где можно показать существование небольшого «эскиза», и это приводит к эффективным алгоритмам.
Но и в этом пространстве все алгоритмы рандомизированы, и существуют сильные детерминированные нижние границы, в основном основанные на сложности коммуникации.
источник