Thomas Jerome Schaefer is an American mathematician. He obtained his Ph.D. in December 1978 from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

, where he worked in the Department of Mathematics. His Ph.D. advisor was Richard M. Karp. He is well-known for his dichotomy theorem, stating that any problem generalizing

Boolean satisfiability In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

in a certain way is either in the complexity class P or is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

References

Year of birth missing (living people) Living people 20th-century American mathematicians American computer scientists University of California, Berkeley alumni 21st-century American mathematicians {{US-mathematician-stub