Narození | 1948 |
---|---|
Smrt | 31. července 2004 |
Státní příslušnost | americký |
Výcvik | Massachusetts Institute of Technology |
Činnosti | Počítačový vědec , inženýr |
Pracoval pro | Kalifornská univerzita v Santa Cruz |
---|---|
Člen | Sdružení pro výpočetní techniku |
Dozorce | Albert R. Meyer |
Ocenění |
ACM Fellow Prix Dijkstra (2007) |
Larry Joseph Stockmeyer (narozen 1948 v Evansville , Indiana , zemřel dne31. července 2004) je americký počítačový teoretik . Patří k průkopníkům v oblasti teorie složitosti a významně přispěl také k distribuovaným výpočtům .
Larry Stockmeyer získal titul B. Sc. V oboru matematiky na Massachusetts Institute of Technology v roce 1972 a titul M. Sc. V oboru elektrotechnika ve stejném roce , rovněž na Massachusetts Institute of Technology. V roce 1974 získal na Massachusetts Institute of Technology pod vedením Alberta R. Meyera titul PhD v oboru počítačových věd s prací „ Složitost rozhodovacích problémů v teorii a logice automatů “ .
V letech 1974 až 1982 pracoval Stockmeyer ve společnosti IBM Research ve výzkumném centru Thomase J. Watsona v Yorktown Heights v New Yorku, poté v letech 1982listopadu 2003ve společnosti IBM Research, Almaden Research Center , San Jose, CA. Nakonec odŘíjen 2002a do roku 2004 působil jako pomocný výzkumný pracovník v oddělení informatiky na Kalifornské univerzitě v Santa Cruz .
Larry Stockmeyer přispěl k teorii složitosti v počítačové vědě od jejího vzniku počátkem 70. let, zejména pokud jde o NP-úplné problémy . Je to článek Problém ekvivalence pro regulární výrazy s kvadráty vyžaduje exponenciální prostor s Albertem R. Meyerem, který zavádí polynomiální hierarchii . Tyto Turingovy střídavé stroje byly zavedeny s Ashok K. Chandra a Dexter Kozen . Aplikace se nacházejí v jednoznačných konečných automatech a dalších problémech se složitostí. S Michaelem Gareym a Davidem S. Johnsonem uvažuje o složitosti hamiltonovských grafů . S Moni Naor pracuje na Ramseyově teorii ; s Cynthií Dworkovou a Nancy Lynchovou vyhrál Dijkstra Prize v roce 2007.