Thomas Jerome Schaefer

Thomas Jerome Schaefer is an American mathematician.

Thomas Jerome Schaefer
Alma materUniversity of California, Berkeley
Known forSchaefer's dichotomy theorem
Scientific career
FieldsComputational complexity theory,
Game theory
InstitutionsUniversity of California, Berkeley
ThesisThe Complexity of Some Two-Person Perfect-Information Games (1978)
Doctoral advisorRichard M. Karp

He obtained his Ph.D. in December 1978 from the University of California, Berkeley, where he worked in the Department of Mathematics. His Ph.D. advisor was Richard M. Karp.[1][2][3][4]

He is well-known for his dichotomy theorem, stating that any problem generalizing Boolean satisfiability in a certain way is either in the complexity class P or is NP-complete.[5]

References

  1. Thomas Jerome Schaefer at the Mathematics Genealogy Project
  2. https://math.berkeley.edu/people/grad/thomas-jerome-schaefer
  3. Thomas J. Schaefer (1978). "On the Complexity of Some Two-Person Perfect-Information Games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4. MR 0490917.
  4. Thomas J. Schaefer (1976). "Complexity of Decision Problems Based on Finite Two-Person Perfect-Information Games". Eighth Annual ACM Symposium on Theory of Computing. ACM. pp. 41–49. MR 0451853.
  5. Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. MR 0521057.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.