Шмуэль Сафра - Shmuel Safra

Шмуэль Сафра (иврит: שמואל ספרא) - израильский ученый-компьютерщик. Он профессор Информатика в Тель-авивский университет, Израиль. Он родился в Иерусалим.

Области исследований Safra включают: теория сложности и теория автоматов. Его работа по теории сложности включает в себя классификацию проблем аппроксимации, показывая их NP-жесткий даже для слабых факторов приближения - и теория вероятностно проверяемые доказательства (PCP) и Теорема PCP, что дает более сильную характеризацию класса НП, через доказательство принадлежности, которое можно проверить, прочитав только постоянное количество его битов.

Его работа по теории автоматов исследует детерминированность и дополнение конечные автоматы над бесконечными строками, в частности, сложность такого перевода для Büchi автоматы, Уличные автоматы и Автоматы Рабина.

В 2001 году Сафра выиграла Премия Гёделя в области теоретической информатики за его статьи «Интерактивные доказательства и трудность аппроксимирующих клик» и «Вероятностная проверка доказательств: новая характеристика NP».

Смотрите также

• Проблема покрытия вершины
• Установить проблему с крышкой

внешняя ссылка

• Домашняя страница Мули Сафры
• Презентации по теории вычислительной сложности
• Шмуэль Сафра на Проект "Математическая генеалогия"