Томас Джером Шефер
Томас Джером Шефер | |
|---|---|
| Альма-матер | Калифорнийский университет, Беркли |
| Известный | Теорема Шефера о дихотомии |
| Научная карьера | |
| Поля | Теория сложности вычислений , Теория игр |
| Учреждения | Калифорнийский университет, Беркли |
| Диссертация | Сложность некоторых игр с идеальной информацией для двух человек (1978) |
| Докторантура | Ричард М. Карп |
Томас Джером Шефер — американский математик.
Он получил докторскую степень. в декабре 1978 года окончил Калифорнийский университет в Беркли , где работал на кафедре математики. Его доктор философии. советником был Ричард М. Карп . [1] [2] [3] [4]
Он хорошо известен своей теоремой о дихотомии , утверждающей, что любая задача, обобщающая булеву выполнимость, определенным образом находится либо в классе сложности P , либо является NP-полной . [5]
Ссылки [ править ]
- ^ Томас Джером Шефер в проекте математической генеалогии
- ^ «Томас Джером Шефер | Кафедра математики Калифорнийского университета в Беркли» .
- ^ Томас Дж. Шефер (1978). «О сложности некоторых игр двух лиц с совершенной информацией» . Журнал компьютерных и системных наук . 16 (2): 185–225. дои : 10.1016/0022-0000(78)90045-4 . МР 0490917 .
- ^ Томас Дж. Шефер (1976). «Сложность задач принятия решений на основе конечных игр двух лиц с совершенной информацией». Восьмой ежегодный симпозиум ACM по теории вычислений . АКМ. стр. 41–49. МР 0451853 .
- ^ Шефер, Томас Дж. (1978). «Сложность задач выполнимости» (PDF) . Учеб. 10-я Энн. ACM симп. по теории вычислений . стр. 216–226. МР 0521057 .
| Базы данных авторитетного контроля : академики |
|---|
   | Эта статья об американском математике незавершена . Вы можете помочь Википедии, расширив ее . |