Thomas Jerome Schaefer - Thomas Jerome Schaefer - Wikipedia

Thomas Jerome Schaefer
Alma materUniversity of California, Berkeley
Známý jakoSchaeferova věta o dichotomii
Vědecká kariéra
PoleTeorie výpočetní složitosti,
Herní teorie
InstituceUniversity of California, Berkeley
TezeSložitost některých her pro dvě osoby s dokonalými informacemi (1978)
Doktorský poradceRichard M. Karp

Thomas Jerome Schaefer je americký matematik.

Získal titul Ph.D. v prosinci 1978 z University of California, Berkeley, kde pracoval na katedře matematiky. Jeho Ph.D. poradce byl Richard M. Karp.[1][2][3][4]

On je známý pro jeho teorém o dichotomii s uvedením, že jakýkoli problém zobecňující Booleovská uspokojivost určitým způsobem je buď v třída složitosti P nebo je NP-kompletní.[5]

Reference

  1. ^ Thomas Jerome Schaefer na Matematický genealogický projekt
  2. ^ https://math.berkeley.edu/people/grad/thomas-jerome-schaefer
  3. ^ Thomas J. Schaefer (1978). „O složitosti některých her pro dvě osoby s dokonalými informacemi“. Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4. PAN  0490917.
  4. ^ Thomas J. Schaefer (1976). "Složitost rozhodovacích problémů založených na konečných dvoučlenných hrách s dokonalými informacemi". Osmý ročník ACM symposia o teorii práce s počítačem. ACM. 41–49. PAN  0451853.
  5. ^ Schaefer, Thomas J. (1978). „Složitost problémů s uspokojivostí“ (PDF). Proc. 10. Ann. ACM Symp. o teorii výpočtu. 216–226. PAN  0521057.