| Naștere | 1948 |
|---|---|
| Moarte | 31 iulie 2004 |
| Naţionalitate | american |
| Instruire | Institutul de tehnologie din Massachusetts |
| Activități | Informatician , inginer |
| Lucrat pentru | Universitatea din California la Santa Cruz |
|---|---|
| Membru al | Asociația pentru mașini de calcul |
| Supervizor | Albert R. Meyer |
| Premii |
Premiul Dijkstra Fellow ACM (2007) |
Larry Joseph Stockmeyer (născut în 1948 în Evansville , Indiana , a murit la31 iulie 2004) este un teoretician american al computerului . Este unul dintre pionierii în domeniul teoriei complexității și a adus contribuții importante și în calculul distribuit .
Larry Stockmeyer a obținut un B. Sc. În matematică de la Massachusetts Institute of Technology în 1972 și un M. Sc. În inginerie electrică în același an , tot de la Massachusetts Institute of Technology. În 1974, a obținut un doctorat în informatică de la Massachusetts Institute of Technology, sub supravegherea lui Albert R. Meyer , cu o teză intitulată „ Complexitatea problemelor decizionale în teoria și logica automatelor ” .
Din 1974 până în 1982, Stockmeyer a lucrat la IBM Research , la Centrul de Cercetare Thomas J. Watson , Yorktown Heights, NY, apoi din 1982 lanoiembrie 2003la IBM Research, Almaden Research Center , San Jose, CA. În cele din urmă de laOctombrie 2002și până în 2004, a fost cercetător asociat la Departamentul de Informatică de la Universitatea din California din Santa Cruz .
Larry Stockmeyer a contribuit la teoria complexității în informatică de la apariția sa la începutul anilor 1970, în special asupra problemelor NP-complete . Este articolul Problema de echivalență pentru expresiile regulate cu pătrat necesită spațiu exponențial cu Albert R. Meyer care introduce ierarhia polinomială . Au fost introduse mașinile alternative Turing , cu Ashok K. Chandra și Dexter Kozen . Aplicațiile se găsesc în automatele finite neechivoce și în alte probleme de complexitate. Cu Michael Garey și David S. Johnson, el ia în considerare complexitatea graficelor hamiltoniene . Cu Moni Naor , lucrează la teoria Ramsey ; cu Cynthia Dwork și Nancy Lynch a câștigat Premiul Dijkstra în 2007.