Matemático estadounidense
Thomas Jerome Schaefer es un matemático estadounidense.
Obtuvo su doctorado en diciembre de 1978 en la Universidad de California, Berkeley , donde trabajó en el Departamento de Matemáticas. Su asesor de doctorado fue Richard M. Karp . [1] [2] [3] [4]
Es bien conocido por su teorema de dicotomía , que establece que cualquier problema que generalice la satisfacibilidad booleana de una determinada manera está en la clase de complejidad P o es NP-completo . [5]
Referencias
- ^ Thomas Jerome Schaefer en el Proyecto de Genealogía Matemática
- ^ "Thomas Jerome Schaefer | Departamento de Matemáticas de la Universidad de California en Berkeley".
- ^ Thomas J. Schaefer (1978). "Sobre la complejidad de algunos juegos de información perfecta para dos personas". Journal of Computer and System Sciences . 16 (2): 185–225. doi : 10.1016/0022-0000(78)90045-4 . MR 0490917.
- ^ Thomas J. Schaefer (1976). "Complejidad de problemas de decisión basados en juegos finitos de información perfecta para dos personas". Octavo simposio anual de la ACM sobre teoría de la computación . ACM. págs. 41–49. MR 0451853.
- ^ Schaefer, Thomas J. (1978). "La complejidad de los problemas de satisfacibilidad" (PDF) . Actas del 10.º Simposio Anual de la ACM sobre Teoría de la Computación . págs. 216-226. MR 0521057.
