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

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

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

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

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

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