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

112

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

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

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

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

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

Джошуа Грохов
источник
3
Мне действительно нравится этот вопрос; с нетерпением жду, чтобы увидеть больше ответов.
Randomwalker
1
Существует также «неявная» стоимость абстракции. Вы упоминаете пример цены абстракции при сортировке и то, как эти абстрагированные результаты не применимы к сортировке чисел (что на самом деле может быть сделано даже в O (n) с сортировкой в ​​некоторых случаях). Нижние границы на диаграммах Вороного часто выводятся путем демонстрации линейного сокращения времени от диаграммы Вороного до сортировки списка чисел. И многие геометрические алгоритмы получают нижние границы из этой нижней границы при вычислении вороной.
Росс Снайдер
почему это вики сообщества?
Нанда
1
@nanda: потому что нет единого правильного ответа, и на самом деле вопрос был разработан, чтобы получить много правильных ответов, как мне кажется.
Джошуа Грохов
1
кажется, что вы действительно имеете в виду релаксацию вместо абстракции
vzn

Ответы:

38

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

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

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

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

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

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

randomwalker
источник
учитывая, что функциональное программирование является моделью для больших вычислений данных (см. MapReduce), это замедление потенциально весьма значительно.
Суреш Венкат
5
Ω(nlogn)
1
По крайней мере, статья, упомянутая в этой теме ([Bird, Jones and De Moor, 1997], см. Там для полной ссылки) устанавливает разрыв между энергичной и ленивой оценкой.
Blaisorblade
Для очень больших вычислений данных стоимость ввода-вывода должна доминировать настолько сильно, что логарифмическое замедление вычислений не должно иметь значения, верно?
adrianN
Что вы подразумеваете под порядком оценки?
Либако
28

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

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

  • α,αα

жилль
источник
4
Хотел бы я проголосовать за это несколько раз.
Жак Каретт
26

Ω(m)mZn

Zn

MRA
источник
25

stststmin+maxmin

Пусть будет количеством вершин во входном графе. Эта проблема, как было известно, требует времени в модели сравнения путей Каргера, Коллера и Филлипса , так же, как и проблема кратчайших путей для всех пар. (Модель пути-сравнение поддерживает традиционные алгоритмы, такие как Floyd-Воршалл.) Тем не менее, в отличие от всех пары кратчайших, оказывается, что все-пар узкого место путь может быть решен в менее чем время , используя быстрое матричное умножение.nΩ(n3)O(n2.8)

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

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

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

Дэвид Эппштейн
источник
Спасибо за то, что подчеркнули «парадокс» и недавнюю статью Чана и Потрашку.
Андрас Саламон
17

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

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

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

Piotr
источник
Пожалуйста, исправьте год цитирования с 2006 по 2003 гг.
MS Dousti
@ Садек Дусти: готово. Это вики сообщества, и у вас больше репутации, чем у меня, так что, думаю, вы могли бы это исправить сами ;-)
Blaisorblade 18.10.10
17

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

Ссылка:

Kaveh
источник
15

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

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

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

Если ваши цвета - это не черные квадраты, а целые числа , то вы можете уменьшить цвет, используя методы Коул – Вишкин в раундах связи. Даже если ваши цвета - это огромные битовые строки, такие как целые числа от , вы получите ту же границу .1,2,...,kO(logk)1,2,...,1010kO(logk)

Итог: цена "неправильной" абстракции: против .O(logk)Ω(k)

Юкка Суомела
источник
13

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

Gil Kalai
источник
10

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

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

Суреш Венкат
источник
4
Хотя P против NP не то, что я имел в виду, это не такой плохой пример. Кстати, Arora, Impagliazzo и Vazirani ( cseweb.ucsd.edu/~russell/ias.ps ) предполагают, что ключевым свойством, которое абстрагируется от общей модели оракула, является локальная проверяемость вычислений. В частности, если любой оракул сохраняет локальную проверяемость и то , а если то . Их работа несколько противоречива (я думаю, что это сталкивается с проблемами релятивизации ограниченных классов малого пространства), но я думаю, что это очень интересно. XPXNPXPNPPX=NPXNP=coNP
Джошуа Грохов
10

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

  • Коды исправления ошибок предполагают, что некоторая переоценка предела Шеннона в сетевых ландшафтах подвержена шуму.
  • Абсолютно новое поле сжимающего зондирования подталкивает к реконструкции разнообразных образов, которые мы находим интересным выходом за пределы Шеннона.
Росс Снайдер
источник
Можете ли вы дать некоторые ссылки для этого :)?
Вивек Багария
8

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

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

Рафаэль
источник
5

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

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

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

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

Шимон Торуньчик
источник
2

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

Артем Казнатчеев
источник
Есть ли у вас конкретные примеры того, как это показывает нижнюю границу, которую можно нарушить, «открыв черный ящик»?
Джошуа Грохов
Хорошая сортировка - это пример, где модель дерева решений дает вам n log n, но вы можете поправиться, взглянув на структуру входных данных.
Суреш Венкат
@Suresh: я имел в виду примеры, которые еще не были упомянуты :).
Джошуа Грохов
Извини, моя ошибка.
Суреш Венкат
Ну, иногда у вас может быть относительно хорошая сложность квантового запроса, но нет быстродействующего алгоритма. Примером является проблема скрытой подгруппы, где нам нужно полиномиальное количество запросов, но все же экспоненциальное время (хотя очевидно, что нижняя граница времени не доказана) для любого известного алгоритма [1]. Я думаю, это цена в обратном направлении. [1] arxiv.org/abs/quant-ph/0401083
Артем Казнатчеев
1

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

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

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

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

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

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

Erel Segal Halevi
источник
0

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

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

Артур Б
источник