Річард Джей Ліптон (народився 6 вересня 1946 року) — американо-південноафриканський інформатик, який працює в галузі теорії комп'ютерних наук, криптографії та ДНК-комп'ютингу (обчислень). Р. Ліптон є заступником декана з наукових досліджень, професором та завідувачем кафедри обчислювальної техніки Фредеріка Дж. Стейрі у коледжі обчислювальної техніки Технологічного інституту штату Джорджія.
Теорема Карпа–Ліптона У 1980 році разом з Річардом М. Карпом, Ліптон довів, що якщо задача здійсненності булевих формул (SAT) може бути вирішена за допомогою логічних схем з поліноміальним числом логічних вентилів, то поліноміальна ієрархія зводиться до свого другого рівня.
Оцінка розміру запиту Ліптон та Дж. Ноутон представили адаптивний алгоритм випадкової вибірки для запитів до бази данихRichard J. Lipton, Jeffrey F. Naughton (1990) «Query Size Estimation By Adaptive Sampling», «PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems»Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider (1990) «SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data», який застосовується до будь-якого запиту, для якого відповіді на запит можуть бути розділені на несуміжні підмножини. На відміну від більшості алгоритмів оцінки вибірки, які статично визначають кількість необхідних вибірок, їх алгоритм визначає кількість вибірки на основі розмірів вибірки та прагне підтримувати постійний час роботи (на відміну від лінійного за кількістю вибірки).
Нагороди та почесні звання
Грант Гуггенхайма, 1981 Членство в Асоціації обчислювальної техніки, 1997 член Національної академії інженерних наук Премія Кнута, 2014
Див. також Теорема про планарне розбиття
Джерела «Weddings: Kathryn Farley, Richard Lipton », The New York Times, 5 June 2016.
Посилання Персональний блог «Загублений лист Геделя і P = NP»
Примітки