Примеры цены абстракции?

Теоретическая информатика предоставила несколько примеров «цены абстракции». Два самых выдающихся из них - это устранение и сортировка по Гауссу. А именно:

• Известно, что исключение Гаусса является оптимальным для, скажем, вычисления определителя, если вы ограничиваете операции строками и столбцами в целом [1]. Очевидно, что алгоритм Штрассена не подчиняется этому ограничению, и он асимптотически лучше исключения Гаусса.
• При сортировке, если вы относитесь к элементам списка как к черным ящикам, которые можно только сравнивать и перемещать, то у нас есть стандартная $n \log n$ информационно-теоретическая нижняя граница. Тем не менее, деревья слияния преодолевают это ограничение, насколько я понимаю, умным использованием умножения.

Есть ли другие примеры стоимости абстракции?

Чтобы быть более формальным, я ищу примеры, когда нижняя граница известна безоговорочно в некоторой слабой модели вычислений, но, как известно, нарушается в более сильной модели. Кроме того, слабость слабой модели должна проявляться в форме абстракции , которая, по общему признанию, является субъективным понятием. Например, я не считаю ограничение на монотонные схемы абстракцией. Надеюсь, два приведенных выше примера проясняют, что я ищу.

[1] КЛЮЕВ В.В., КОКОВКИН-ЩЕРБАК Н.И. О минимизации числа арифметических операций для решения линейных алгебраических систем уравнений. Перевод GI TEE: Технический отчет CS 24, июнь t4, t965, Отделение компьютерных наук, Стэнфордский университет.

Еще один прекрасный пример цены абстракции: сетевое кодирование . Известно, что в настройках многоадресной передачи отношение max-flow-min-cut не является равенством (первичное и двойное не совпадают). Тем не менее, традиционные модели предполагают поток, который просто передается и никак не «обрабатывается». С помощью сетевого кодирования вы можете преодолеть этот предел, умело комбинируя потоки. Этот пример был отличным мотиватором для изучения сетевого кодирования в первую очередь.

Чисто функциональное программирование - это популярная абстракция, которая предлагает, по крайней мере, в соответствии со своими сторонниками, значительное увеличение выразительной силы кода, среди других преимуществ. Однако, поскольку это ограничительная модель машины, в частности, не допускающая изменчивую память, возникает вопрос об асимптотическом замедлении по сравнению с обычной (RAM) моделью.

Там отличная нить по этому вопросу здесь . Основные выносы, кажется, являются:

1. Вы можете моделировать изменчивую память с помощью сбалансированного бинарного дерева, поэтому наихудшее замедление - O (log n).
2. С нетерпением оценки есть проблемы, для которых это лучшее, что вы можете сделать.
3. При ленивой оценке неизвестно, есть ли разрыв. Однако существует множество естественных проблем, для которых ни один из известных чисто функциональных алгоритмов не соответствует оптимальной сложности ОЗУ.

Мне кажется, что это удивительно основной вопрос, который нужно открыть.

Хотя ваш вопрос посвящен теории сложности, подобные вещи могут происходить и в других областях, таких как теория языков программирования. Вот пара примеров, когда абстракция делает что-то неразрешимым (то есть нижняя граница в слабой модели невозможна, а сильная модель позволяет выразить алгоритм):

• В лямбда-исчислении есть функции, которые вы не можете выразить напрямую (т. Е. Как лямбда-член, который бета-сводит к желаемому результату). Примером является параллельный или (функция двух аргументов, которая возвращает тот, который заканчивается). Другим примером является функция, которая печатает свой аргумент буквально (функция, очевидно, не может различить два бета-эквивалентных аргумента). Недостаток выразительности связан с применением абстракции о том, что бета-эквивалентные лямбда-термины должны обрабатываться одинаково.

• $\forall\alpha, \alpha\to\alpha$

$\Omega(\sqrt{m})$$m$$\mathbb{Z}_n^*$

$\mathbb{Z}_n^*$

$s$$t$$s$$t$$s$$t$$\min$$+$$\max$$\min$

Пусть будет количеством вершин во входном графе. Эта проблема, как было известно, требует времени в модели сравнения путей Каргера, Коллера и Филлипса , так же, как и проблема кратчайших путей для всех пар. (Модель пути-сравнение поддерживает традиционные алгоритмы, такие как Floyd-Воршалл.) Тем не менее, в отличие от всех пары кратчайших, оказывается, что все-пар узкого место путь может быть решен в менее чем время , используя быстрое матричное умножение.$n$$\Omega(n^3)$$O(n^{2.8})$

Согласно обсуждению этого вопроса , многие проблемы вычислительной геометрии имеют нижние границы в алгебраических моделях дерева решений или алгебраических вычислительных моделей, вытекающих из фундаментальных проблем, таких как сортировка или различение элементов . Нетрудно найти статьи, утверждающие, что верхние оценки для смежных задач, таких как построение триангуляций Делоне, являются оптимальными, поскольку они соответствуют этим нижним границам.$\Omega(n\log n)$$O(n\log n)$

Но когда входные данные указываются в целочисленных декартовых координатах (как это часто практикуется, поскольку плавающая точка плохо подходит для вычислительной геометрии), эти нижние границы не соответствуют вычислительной модели. Возможно, неудивительно, что проблемы типа поиска с ортогональным диапазоном могут быть решены быстрее, используя методы, адаптированные к целочисленной сортировке, но даже у неортогональных задач часто могут быть более быстрые алгоритмы (которые решают проблему точно, в моделях вычислений, допускающих целочисленную арифметику с O (1) ) кратность точности ввода целых чисел). Смотрите, например, arXiv: 1010.1948 для одного набора примеров.

Есть много таких примеров в криптографии, особенно доказательства с нулевым знанием. Смотрите, например, тезис:

Боаз Барак, Не криптографические методы в криптографии, 2003.

(Между прочим, название тезиса обеспечивает доказательство этого комментария с нулевым знанием :)

Деревья алгебраических решений используются в качестве основы в вычислительной геометрии, чтобы показать множество простых задач, таких как уникальность элемента: . Эти нижние оценки затем используются для отображения более сложных задач, таких как диаграммы Вороного, которые также имеют нижние границы . Позже я был удивлен, прочитав алгоритм ожидаемого времени для решения ближайшей пары точек на плоскости, который является обобщением уникальности элемента. Он избегает Алгебраического дерева решений, связанного с помощью хеширования. Я нашел это в книге «Разработка алгоритмов» Кляйна и Тардоса. Существует аналогичный, но более сложный алгоритм для решения той же проблемы, описанной в блоге Р.Дж. Липтона .$\Omega(n \log n)$$\Omega(n \log n)$$O(n)$

Ссылка:

• Ричард Дж. Липтон, « Рабин подбрасывает монету », март 2009 года,
  опубликовано в «Потерянном письме Годеля» и в блоге P = NP .

Рассмотрим синхронные детерминированные распределенные алгоритмы для уменьшения количества цветов в графе цикла с до . То есть вам дается правильная окраска цикла, и вы хотите вывести правильную окраску цикла; каждый узел цикла является процессором.$k$$3$$k$$3$

Если вы предполагаете модель, основанную на сравнении (вы рассматриваете цветов как черные ящики, которые можно передавать только от одного узла к другому и сравнивать друг с другом), вы получите тривиальную нижнюю границу для числа раунды общения.$k$$\Omega(k)$

Тем не менее, эта абстракция, возможно, явно ошибочна: если вы можете что-то передавать в сети связи, у вас будет какой-то способ кодировать «что-то» в виде цепочки битов. И теперь все начинает выглядеть намного лучше.

Если ваши цвета - это не черные квадраты, а целые числа , то вы можете уменьшить цвет, используя методы Коул – Вишкин в раундах связи. Даже если ваши цвета - это огромные битовые строки, такие как целые числа от , вы получите ту же границу .$1, 2, ..., k$$O(\log^* k)$$1, 2, ..., 10^{10^k}$$O(\log^* k)$

Итог: цена "неправильной" абстракции: против .$O(\log^* k)$$\Omega(k)$

Пример, который приходит мне в голову - это вычисление объема. В результате Барани и Фурэди вам нужно экспоненциальное количество запросов, и есть алгоритм рандомизированного полиномиального времени Дайера-Фриза-Каннана . Разрыв представляет собой приз абстракции, а также выгоду случайности, но я думаю, что основной причиной разрыва является цена абстракции. (Надеюсь, я понял вопрос, и он идет в правильном направлении.)

Это, вероятно, не совсем то, что вы имели в виду. Но в определенном смысле независимость P против NP от оракулов является таким примером. На самом деле это говорит о том, что если все, что вас волнует, это моделирование и перечисление (т.е. если это ваша «модель» вычислений), то вы не можете разделить эти классы или свернуть их.

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

Теорема отсчетов Шеннона-Найквиста предлагает достаточное условие для теоретико-информационных границ коммуникации. Теория выборки основана на примерах, где входящий сигнал имеет компактное / случайное представление. Недавние успехи в выборке показывают, что эта абстракция, возможно, имеет свою цену - что виды измерения, которые мы заинтересованы в измерении, обычно имеют разреженные представления, так что эти границы не являются жесткими. Кроме того, информация может быть закодирована гораздо плотнее, чем первоначально предполагалось.

• Коды исправления ошибок предполагают, что некоторая переоценка предела Шеннона в сетевых ландшафтах подвержена шуму.
• Абсолютно новое поле сжимающего зондирования подталкивает к реконструкции разнообразных образов, которые мы находим интересным выходом за пределы Шеннона.

Многие интересные проблемы, с которыми сталкиваются естественные науки, оказываются NP-сложными в классическом смысле. Хотя это понятие теоретически совершенно верно, оно никак не помогает биологу или физику. Мы находим, что некоторые NP-трудные задачи поддаются лечению с фиксированным параметром и часто с параметром, который, как считается, ограничен небольшой константой в реальном мире.

То есть TCS говорит нам, что мы не ожидаем эффективного решения абстрактной проблемы, но мы можем быстро решить возникающие случаи - довольно большой разрыв.

В этой статье http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf мы изучили машины Тьюринга, которые имеют ограниченный доступ к данным. Это формализовано как инвариантный относительно автоморфизмов реляционной структуры; Например, в нижней границе O (n log n) для сортировки вы бы сказали, что машина может обрабатывать и хранить рациональные числа, но ее переходы должны быть инвариантными относительно автоморфизмов (Q, <), то есть монотонных биекций. Формальное определение является более сложным, чтобы точно указать, какие структуры данных может хранить машина в своей памяти (
в некотором смысле она должна быть «конечной» , но мы разрешаем хранить более сложные структуры, чем только наборы значений данных, такие как неупорядоченные кортежи).

В статье мы доказали некоторые нижние оценки для других машин Тьюринга с «ограниченным доступом к данным». В частности, мы показали, что:

• Детерминированная машина Тьюринга, которая может обрабатывать векторы (скажем, над полем из двух элементов), но может использовать только тесты на сложение векторов и равенство, не может определить за полиномиальное время, является ли данный список векторов линейно зависимым (формально, переходы машин должны быть инвариантным относительно автоморфизмов векторного пространства). Это противоположно недетерминированным машинам, которые могут просто угадать комбинацию векторов, которая в сумме равна 0. Заметим, что удаление по Гауссу выполняется за полиномиальное время, но имеет доступ к координатам векторов; в частности, его переходы не инвариантны относительно автоморфизмов векторного пространства.

• В подходяще определенной модели машины Тьюринга, которые могут сравнивать натуральные числа только по равенству (даже не <), не могут быть определены. Здесь мы рассмотрим реляционную структуру (N, =) и машины, инвариантные относительно ее автоморфизмов. Существует конструкция (похожая на конструкцию Кая-Фюрера-Иммермана из теории конечных моделей), которая показывает, что на самом деле в этой модели P ≠ NP. Разрешение машинам сравнивать числа с помощью <дает им достаточную мощность для определения.

Общая цена абстракции присутствует в структурах черного ящика, таких как сложность дерева решений или сложность квантовых запросов. Если мы ограничим анализ этими моделями, то часто сможем найти очень хорошие оценки сложности задач. Фактически, для квантового запроса мы можем в основном решить сложность задач, потому что метод отрицательного противника обеспечивает жесткие нижние границы (в пределах коэффициента log n / loglog n: 1005.1601 ). Это дает нам отличный инструмент для анализа сложности запросов, но часто становится трудно сравнивать сложность запроса с более стандартной сложностью времени / пространства машины Тьюринга (кроме как в виде грубой нижней границы).

Вот два примера, оба относятся к непрерывным и дискретным моделям:

1. Предположим, что есть (бесконечно малое) сокровище, спрятанное в интервале , в позиции . Мы хотим найти сокровище, копая. Всякий раз, когда мы копаем в позиции , мы получаем обратную связь о том, , или . Очевидно, что если может быть любым действительным числом, то любой алгоритм поиска может никогда не завершиться. может быть очень маленьким, но мы никогда не достигнем . x y x < y x = y x > y x | х - у | у = $[0,1]$$x$$y$$x<y$$x=y$$x>y$$x$$|x-y|$$y=x$

   Тем не менее, мы можем расширить поисковую модель, чтобы обеспечить непрерывную развертку. В этой модели мы просто позволяем работать непрерывно в интервале и получать обратную связь всякий раз, когда .[ 0 , 1 ] y = $y$$[0,1]$$y=x$

2. Мотивация для проблемы А исходит от проблемы разделения тортов без зависти . Стромквист показал , что никакой конечный протокол (даже если он не ограничен) не может гарантировать разделение пирога без зависти между тремя и более игроками, если каждый игрок должен получить одну соединенную фигуру.

   Однако, как объяснили Ауманн и Домбб позже , этот результат применяется только к дискретной модели резки, где «На каждом шаге протокол выбирает игрока и действительное число и предлагает игроку сделать отметку в уникальной точке для которого ",", а не для случаев, когда, например, какой-то посредник обладает полной информацией о функциях оценки игроков и предлагает деление на основе этой информации ". α i x v i ( 0 , x ) = $i$$\alpha$$i$$x$$vi(0,x) = \alpha$

   Кроме того, результат не относится к алгоритмам с непрерывными операциями, таким как процедуры с подвижным ножом.

Когда это выражено в логике первого порядка, любое доказательство принципа голубя для фиксированного n имеет экспоненциальную длину. Однако с помощью арифметики доказательство может быть выражено гораздо более кратко.

Успех решателей SMT обусловлен отказом от абстрактной модели сокращения проблем до SAT, позволяющей более богатым теориям значительно сократить количество необходимых вычислений.