Майкл Сипсер
- Майкл Фредрик Сипсер — американский ученый-теоретик в области компьютерных наук.
- Сипсер внес значительный вклад в теорию сложности вычислений.
- Он является профессором прикладной математики и деканом факультета естественных наук Массачусетского технологического института.
- Сипсер специализируется на алгоритмах и теории сложности, включая эффективные коды с исправлением ошибок, интерактивные системы проверки, случайность, квантовые вычисления и определение вычислительной сложности задач.
- Он представил метод вероятностного ограничения для доказательства нижних границ сложности схемы для суперполиномов.
- Сипсер установил связь между расширяющими графами и дерандомизацией и представил расширяющие коды, приложение расширяющих графов.
- Он доказал, что Go является сложным пространством.
- В теории квантовых вычислений Сипсер представил адиабатический алгоритм.
- Сипсер уже давно интересуется проблемой соотношения P и NP и в 1975 году поспорил с Леонардом Адлеманом на унцию золота, что проблема будет решена к концу 20-го века.
Полный текст статьи: