Самые влиятельные результаты Липтона

30

Ричард Дж. Липтон был выбран в качестве лауреата Кнутской премии 2014 года «За внедрение новых идей и методов».

Каковы, на ваш взгляд, основные новые идеи и методы, разработанные Липтоном?

Заметка. Этот вопрос должен стать вики сообщества, пожалуйста, поставьте одну такую ​​идею, технику или результат для ответа.

Bruno
источник
11
Поздравляем Ричарда Дж. Липтона! :-)
Марцио Де Биаси,
Блог RJLipton (~ 5 лет) со ссылками на его книги / исследования и т. Д.
vzn
1
Было бы неплохо, если кто-нибудь напишет что-нибудь о сложности многопартийной коммуникации и числе на модели лба. У меня нет времени в настоящее время.
Сашо Николов
Вот ссылка на Лекцию Премии Кнута: techtalks.tv/talks/…
Майкл Вехар,
1
Есть еще две статьи, которые здесь не упомянуты, и у обеих есть более 500 ссылок на Google Scholar: scholar.google.com/… ( Aleliunas et al., На L против NL, важная статья сложности) и scholar.google.com/… (De Милло и др почему тестирование, возможно , лучше , чем формальные доказательства правильности программ -.! спорная)
Андраш Саламон

Ответы:

34

Планарная Сепаратор теорема утверждает , что в любом плоском n -vertex граф г существует множество вершины, удаление которых оставляет граф разъединенным по крайней мере на две примерно сбалансированные компоненты. Более того, такой набор можно найти за линейное время. Этот (жесткий) результат,доказанный Липтоном и Тарьяном(улучшенный по сравнению с предыдущим результатом Унгаром), является мощным инструментом для разработки алгоритмов на плоских графах. Это дает много точных субэкспоненциальных алгоритмов времени для NP-трудных задач и улучшенных алгоритмов аппроксимации полиномиального времени. Просмотрстраницы википедиидает хорошую отправную точку для изучения многочисленных приложений. Раннее исследованиес подробной информацией о ряде приложений было написано Lipton и Tarjan в 1980 году.О(N)

Сашо Николов
источник
2
Почти все эти алгоритмы основаны на методах декомпозиции, а не на плоском разделителе. Также есть много вариантов доказательства этой теоремы о разделителях, мы должны сказать спасибо всем этим изобретателям доказательств. В том, как вы говорили о разделителе, мы должны сказать спасибо парню, который первым нашел числа (они сначала даже не нашли маленький плоский разделитель, они просто улучшили старые). Обратите внимание, что в разложениях нам нужны более специальные виды разделителей. Техники разложения в основном получены работами Робертсона и Сеймура, которые обычно работают даже на исключенных несовершеннолетних.
Саид
14
@ Как обычно, ты выглядишь странно агрессивно. Это вики сообщества, не стесняйтесь улучшать ответ по своему усмотрению. Я добавил, что они не обнаружили небольших плоских сепараторов. Насколько мне известно, для каждого приложения, которое я упоминаю, есть пример, который работает с помощью теоремы о плоском разделителе (и ряд примеров можно найти в обзоре 1980 года Липтона и Тарьяна). Это не означает, что другие инструменты не нужны или других методов не существует. Статья Липтона и Тарьяна предшествует результатам Алона, Робертсона и Сеймура на 10+ лет.
Сашо Николов
3
@Seed также я не могу поверить, что вы прямо скажете, что теорема о плоском разделителе играет в этих приложениях не более существенную роль, чем построение натуральных чисел. Это смешно!
Сашо Николов
9
В любом случае, давайте попробуем быть более конструктивными. Граф Менорс I с 1983 года, и это первая статья Робертсона и Сеймура вместе, так что я не вижу в этом вашей точки зрения. В любом случае, я не отрицаю, что эти идеи были раньше: результат Унгара относится к 1950-м годам. Дело в том, что доказательство жесткой границы было знаковым результатом, и существует ряд точных алгоритмов и алгоритмов аппроксимации, которым требуется только теорема Липтона и Тарьяна или разложения, которые используют ее в качестве черного ящика. Обследование 1980 года уже дает немало примеров (предшествующих графу несовершеннолетних I).
Сашо Николов
3
Их результат очень хороший (как и многие другие хорошие результаты), но формулировка этого ответа так сильно преувеличивает. Например, планарный разделитель на самом деле не является основным инструментом для решения сложной проблемы в плоских графах, по крайней мере в наши дни, когда существует множество методов декомпозиции для более общего сценария. Также я хочу подчеркнуть, что их работа пока великолепна, но не так велика даже в их время (+ -5 лет). Все, что я сказал в этих двух комментариях, просто повторяет мои предыдущие слова только потому, что вы и еще как минимум 4 любите делать личные атаки.
Саид
26

Теорема Карпа-Липтона гласит, что не может иметь булевы схемы полиномиального размера, если полиномиальная иерархия не рухнет на второй уровень.Nп

Два следствия этой теоремы для теории сложности:

  • вероятно, не имеет логических схем полиномиального размера; Поэтому доказательство нижних границ размеров схем является возможным подходом для разделения классов сложности.Nп
  • Несколько результатов основаны на этой теореме для доказательства разделения классов сложности (например, теорема Каннана).
Бруно
источник
23

Случайная самовосстанавливаемость перманента . Липтон показал, что если существует алгоритм, который правильно вычисляет перманент дроби всех F n × n , где F - конечное поле размером не менее 3 n , то этот алгоритм можно использовать как черный ящик для вычисления перманента любой матрицы с высокой вероятностью.1-1/(3N)FN×NF3N

Основная идея заключается в том, что перманент является многочленом низкой степени, поэтому его композиция с одномерной аффинной функцией является одномерным многочленом низкой степени (по x ) и может быть получена точно из небольшого числа значений с помощью интерполяции. , Вы можете выбрать случайный B так, чтобы композиция распределялась как перманент случайной матрицы для любого x . При х = 0 одномерный полином только перманент А . Подробности можно найти в главе 8 Арора Барак .A+ИксВИксВИксИксзнак равно0A

Этот алгебраический подход был чрезвычайно влиятельным в теории сложности. Идеи Липтона привели в конечном итоге к доказательству теоремы IP = PSPACE, доказательству теоремы PCP и к результатам по локальным кодам с исправлением ошибок.

Сашо Николов
источник
16

Я не уверен на 100%, является ли приведенное ниже объяснение исторически точным. Если это не так, пожалуйста, не стесняйтесь редактировать или удалять.

Мутация была изобретена Липтоном. Мутационное тестирование можно рассматривать как способ измерения качества или эффективности тестового набора. Основная идея заключается в том, чтобы внедрить ошибки в тестируемую программу (то есть, чтобы изменить программу), предпочтительно виды ошибок, которые может совершить программист-человек, и посмотреть, обнаружит ли набор тестов введенные ошибки. Типичным примером такого рода тестирования мутаций может быть замена x> 0 на x <0 или замена x на x + 1 или x-1. Доля ошибок, обнаруженных набором тестов, является «показателем адекватности мутаций» набора тестов. Говоря очень свободно, можно думать об этом как о методе Монте-Карло для вычисления показателя адекватности мутации.

Более абстрактно можно сказать, что мутационное тестирование выдвигает на первый план симметрию или двойственность между программой и ее наборами тестов: не только можно использовать набор тестов, чтобы стать более уверенным в правильности программы, но, наоборот, программа может быть используется для получения уверенности в качестве тестового набора.

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

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

История . Из (1): История мутационного тестирования восходит к 1971 году в студенческой статье Ричарда Липтона [...] Рождение поля также может быть идентифицировано в других работах, опубликованных в конце 1970-х годов Липтоном и соавторами. (2), а также Гамлет (3).

  1. Репозиторий мутационного тестирования: теория мутационного тестирования .

  2. RA DeMillo, RJ Lipton, FG Sayward, Советы по выбору тестовых данных: Справка для практикующего программиста .

  3. Р.Г. Гамлет. Тестирование программ с помощью компилятора .

  4. S. Berghofer, T. Nipkow, Случайное тестирование в Изабель / HOL. ,

Мартин Бергер
источник
15

Лемма Шварца - Циппеля - Демилло-Липтона - фундаментальный инструмент арифметической сложности: в основном говорится, что если вы хотите узнать, представляет ли арифметическая схема нулевой полином, все, что вам нужно, - это оценить схему на одном входе. Тогда вы получите ненулевое значение с хорошей вероятностью, если схема не представляет нулевой полином.

Это особенно важная лемма, поскольку для этой проблемы не известен детерминированный алгоритм за полиномиальное время.

Лемма обычно известна как лемма Шварца-Циппеля . Историю этой леммы можно найти в собственном блоге Липтона .

Bruno
источник
4
Как указано в комментарии, похороненном в нижней части этого поста в блоге, стоит упомянуть, что важный особый случай этой леммы восходит по крайней мере к 1922 году, когда она была доказана Рудой (см. «Конечные поля» Лидля и Нидеррейтера, Теорема 6.13 и примечания к главе).
Эшли Монтанаро
13

Уязвимость в системах сложения векторов EXPSPACE-трудна : в RJ Lipton, проблема достижимости требует экспоненциального пространства , Отчет об исследовании 63, Йельский университет, 1976.

Система сложения векторов (VAS, эквивалентная сети Петри) размерности определяется как пара (обратите внимание, что ни один компонент v ′ не может быть отрицательным). Проблема совместимости с учетом VAS и целевого вектораdv0,Av0NdAZdNdvvuAv=v+uvvNdv0v1vnvnvNdvn(i)v(i)1id, В сочетании с верхней границей EXPSPACE, доказанной C. Rackoff в 1978 году , результат Липтона показывает полноту для EXPSPACE.

vn=v

Сильвен
источник
5

Сложность многопартийной коммуникации и модель «число на лбу» были представлены Ашоком К. Чандрой , Мерриком Л. Фёрстом и Ричардом Дж. Липтоном в Многопартийных протоколах , STOC 1983, doi: 10.1145 / 800061.808737 .

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

kkn

n

NkNk=3NO(logN)Nk(2n1)O(n)

0

N

Андраш Саламон
источник
Выглядит очень хорошо, спасибо за то, что выполнили мое предложение.
Сашо Николов