Липтон, Ричард

В 1968 году Липтон получил диплом бакалавра по математике в Университете Кейс Вестерн резерв.

В 1973 году получил степень доктора философии в Университете Карнеги — Меллона. Темой диссертации под руководством Дэвида Парнаса^[2] было On Synchronization Primitive Systems.

С 1973 по 1978 год он преподавал в Йельском университете, потом — в Беркли (1978—1980) и Принстоне (1980—2000) (где начал работать в области ДНК-вычислений).

С 1996 года являлся главным научным консультантом в Telcordia Technologies.

С 2000 по 2018 год работал профессором в Технологическом институте Джорджии, с 2018 года является почётным профессором (эмеритом)^[3].

Является заведующим кафедрой вычислительной техники Фредерика Стори в колледже вычислительной техники.

Под его руководством защитили диссертации около 20 аспирантов, среди которых лауреат премии Тьюринга Ави Вигдерсон и криптограф Дэн Боне.

Ричард Липтон внёс значительный вклад в теорию сложности вычислений и разработку алгоритмов^[4]. В 1980 году совместно с Ричардом Карпом он доказал теорему Карпа — Липтона. Она утверждает, что если задача выполнимости булевых формул (SAT) может быть решена с помощью булевых схем полиномиального размера, то полиномиальная иерархия коллапсирует до второго уровня^[5].

Совместно с Робертом Тарьяном Липтон доказал теорему о плоском сепараторе (теорему Липтона — Тарьяна). Согласно этому результату, любой планарный граф с ${\displaystyle n}$ вершинами можно разделить на две примерно равные части путём удаления ${\displaystyle O({\sqrt {n}})}$ вершин. Эта теорема стала основой для разработки множества эффективных алгоритмов, использующих стратегию «разделяй и властвуй».

Кроме того, Липтон разработал концепцию тестирования программ, что оказало влияние на развитие теории интерактивных доказательств^[6].

Ричард Липтон является одним из пионеров в области ДНК-вычислений. В 1995 году в журнале Science он опубликовал статью «DNA solution of hard computational problems», в которой теоретически показал возможность использования молекул ДНК для решения NP-полной задачи выполнимости булевых формул (SAT). Совместно с результатами Леонарда Адлемана этот подход сформировал «модель Адлемана — Липтона», ставшую основой для многих последующих исследований в этой сфере^[4].^[7]

Ричард Липтон совместно с Кеннетом Реганом ведёт блог «Gödel's Lost Letter and P=NP». Блог посвящён теоретической информатике, проблеме равенства классов P и NP, а также обсуждению открытых проблем и истории науки^[8].^[9].

• 1981 — Стипендия Гуггенхайма
• 1997 — действительный член Ассоциации вычислительной техники^[10]
• 1999 — член Национальной инженерной академии США^[11]
• 2014 — Премия Кнута^[12]
• 2014 — член Американской академии искусств и наук

Книги:

• «The P=NP Question and Gödel's Lost Letter» (2010)
• «Quantum Algorithms via Linear Algebra: A Primer»

Ключевые статьи:

• «A separator theorem for planar graphs» (1979)^[13]
• «DNA solution of hard computational problems» (1995)^[13]