Thomas Jerome Schaefer is an American mathematician.
Thomas Jerome Schaefer | |
|---|---|
| Alma mater | University of California, Berkeley |
| Known for | Schaefer's dichotomy theorem |
| Scientific career | |
| Fields | Computational complexity theory, Game theory |
| Institutions | University of California, Berkeley |
| Thesis | The Complexity of Some Two-Person Perfect-Information Games (1978) |
| Doctoral advisor | Richard 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
edit- ^ Thomas Jerome Schaefer at the Mathematics Genealogy Project
- ^ "Thomas Jerome Schaefer | Department of Mathematics at University of California Berkeley".
- ^ 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.
- ^ 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.
- ^ Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. MR 0521057.
