Томас Джером Шефер

американский математик

Томас Джером Шефер — американский математик.

Он получил докторскую степень в декабре 1978 года в Калифорнийском университете в Беркли , где работал на кафедре математики. Его научным руководителем по докторской степени был Ричард М. Карп . ^{[1] [2] [3] [4]}

Он хорошо известен своей теоремой о дихотомии , утверждающей, что любая задача, обобщающая булеву выполнимость определенным образом, либо находится в классе сложности P , либо является NP-полной . ^[5]

Ссылки

1. Томас Джером Шефер в проекте «Генеалогия математики»
2. «Томас Джером Шефер | Кафедра математики Калифорнийского университета в Беркли».
3. Томас Дж. Шефер (1978). «О сложности некоторых игр двух лиц с полной информацией». Журнал компьютерных и системных наук . 16 (2): 185–225. doi : 10.1016/0022-0000(78)90045-4 . MR  0490917.
4. Томас Дж. Шефер (1976). «Сложность задач принятия решений на основе конечных игр двух лиц с полной информацией». Восьмой ежегодный симпозиум ACM по теории вычислений . ACM. стр. 41–49. MR  0451853.
5. Шефер, Томас Дж. (1978). «Сложность проблем выполнимости» (PDF) . Proc. 10th Ann. ACM Symp. on Theory of Computing . стр. 216–226. MR  0521057.