Ричард Джей Липтон (родился 6 сентября 1946 года) — американский учёный-компьютерщик , заместитель декана по исследованиям, профессор и заведующий кафедрой Фредерика Г. Стори в области вычислительной техники в Колледже вычислительной техники Технологического института Джорджии . Он работал в области теории вычислительной техники , криптографии и ДНК-вычислений .
В 1968 году Липтон получил степень бакалавра по математике в Университете Кейс Вестерн Резерв . В 1973 году он получил степень доктора философии в Университете Карнеги-Меллона ; его диссертация под руководством Дэвида Парнаса называется « О примитивных системах синхронизации» . После окончания университета Липтон преподавал в Йельском университете в 1973–1978 годах, в Беркли в 1978–1980 годах, а затем в Принстоне в 1980–2000 годах. С 2000 года Липтон работает в Технологическом институте Джорджии . Во время работы в Принстоне Липтон работал в области ДНК-вычислений . С 1996 года Липтон является главным научным консультантом в Telcordia . В 1999 году Липтон был избран членом Национальной инженерной академии за применение теории компьютерных наук на практике.
В 1980 году Липтон совместно с Ричардом М. Карпом доказал, что если задачу SAT можно решить с помощью булевых схем с полиномиальным числом логических элементов , то полиномиальная иерархия схлопывается до своего второго уровня.
Демонстрация того, что программа P имеет некоторое свойство, является простым процессом, если действия внутри программы являются непрерываемыми. Однако, когда действие прерываемо, Липтон показал, что с помощью определенного типа редукции и анализа можно показать, что сокращенная программа имеет это свойство тогда и только тогда, когда исходная программа имеет это свойство. [2] Если редукция выполняется путем рассмотрения прерываемых операций как одного большого непрерывного действия, даже при этих смягченных условиях свойства могут быть доказаны для программы P. Таким образом, доказательства корректности параллельной системы часто могут быть значительно упрощены.
Липтон изучал и создавал модели безопасности баз данных о том, как и когда ограничивать запросы, сделанные пользователями базы данных, чтобы не допустить утечки личной или секретной информации. [3] Например, запрос базы данных пожертвований на избирательные кампании может позволить пользователю обнаружить отдельные пожертвования политическим кандидатам или организациям. Если предоставить доступ к средним значениям данных и неограниченный доступ к запросам, пользователь может использовать свойства этих средних значений для получения незаконной информации. Считается, что эти запросы имеют большое «перекрытие», что создает небезопасность. Ограничивая «перекрытие» и количество запросов, можно добиться защищенной базы данных.
Ричард Липтон и Эндрю Томкинс представили рандомизированный алгоритм онлайн-интервального планирования , версия с размером 2 оказалась весьма конкурентоспособной, а версия с размером k достигла O(log ), а также продемонстрировала теоретическую нижнюю границу O(log ). [4] Этот алгоритм использует частную монету для рандомизации и «виртуальный» выбор, чтобы обмануть противника среднего уровня .
Пользователю, представленному событием, необходимо решить, включать ли его в расписание. Виртуальный алгоритм 2-го размера описывается тем, как он реагирует на 1-интервал или k -интервалы, представленные противником:
Опять же, этот алгоритм 2-размера показывает, что он сильно конкурентен . Затем показано, что обобщенный алгоритм k -размера, который похож на алгоритм 2-размера, показывает, что он O(log )-конкурентен.
Липтон показал, что рандомизированное тестирование может быть доказуемо полезным, если проблема удовлетворяет определенным свойствам. [5] Доказательство правильности программы является одной из самых важных проблем, представленных в информатике. Обычно при рандомизированном тестировании, чтобы достичь 1/1000 вероятности ошибки, необходимо запустить 1000 тестов. Однако Липтон показывает, что если проблема состоит из «легких» подчастей, повторное тестирование методом черного ящика может достичь c r частоты ошибок, где c — константа, меньшая 1, а r — количество тестов. Следовательно, вероятность ошибки экспоненциально быстро стремится к нулю по мере роста r .
Этот метод полезен для проверки правильности решения многих типов задач.
В области теории игр , а точнее некооперативных игр , Липтон совместно с Э. Маркакисом и А. Мехтой доказали [6] существование стратегий эпсилон-равновесия с носителем, логарифмическим по числу чистых стратегий . Более того, выигрыш таких стратегий может эпсилон-аппроксимировать выигрыши точных равновесий Нэша . Ограниченный (логарифмический) размер носителя обеспечивает естественный квазиполиномиальный алгоритм для вычисления эпсилон-равновесий .
Липтон и Дж. Нотон представили адаптивный алгоритм случайной выборки для запросов к базе данных [7] [8] , который применим к любому запросу, ответы на который можно разбить на непересекающиеся подмножества [ необходимо разъяснение ] . В отличие от большинства алгоритмов оценки выборки, которые статически определяют количество необходимых выборок, их алгоритм определяет количество выборок на основе размеров выборок и стремится поддерживать постоянное время выполнения (в отличие от линейного по количеству выборок).
Демилло , Липтон и Перлис [9] критиковали идею формальной проверки программ и утверждали, что
Чандра, Ферст и Липтон [10] обобщили понятие двухсторонних протоколов связи до многосторонних протоколов связи. Они предложили модель, в которой набор процессов ( ) имеет доступ к набору целых чисел ( , ) за исключением одного из них, так что доступ к запрещен . Этим процессам разрешено общаться, чтобы прийти к консенсусу по предикату. Они изучили сложность связи этой модели, определяемую как количество бит, переданных между всеми процессами. В качестве примера они изучили сложность k -стороннего протокола для Exactly -N (все ли 's в сумме равны N?), и получили нижнюю границу с помощью метода тайлинга. Они также применили эту модель для изучения общих ветвящихся программ и получили нижнюю границу времени для ветвящихся программ с постоянным пространством, которые вычисляют Exactly- N .
У нас нет способа доказать, что задача выполнимости булевых уравнений (часто сокращенно SAT), которая является NP-полной , требует экспоненциального (или, по крайней мере, суперполиномиального) времени (это знаменитая задача P против NP ) или линейного (или, по крайней мере, суперлогарифмического) пространства для решения. Однако в контексте компромисса между пространством и временем можно доказать, что SAT не может быть вычислена, если мы применяем ограничения как ко времени, так и к пространству. Л. Фортноу , Липтон, Д. ван Мелкебек и А. Виглас [11] доказали, что SAT не может быть вычислена машиной Тьюринга , которая требует не более O( n 1.1 ) шагов и не более O( n 0.1 ) ячеек ее лент чтения-записи.
