Jelaskan Perjalanan Hidup dari Stephen Cook

Cook memperoleh gelar sarjana pada tahun 1961 dalam ilmu komputer dari University of Michigan, gelar master pada tahun 1962 dan doktor pada tahun 1966 dalam ilmu matematika di Universitas Harvard.                 Ia bergabung dengan University of California, Berkeley, departemen matematika pada tahun 1966.   sebagai asisten profesor, dan tinggal di sana sampai tahun 1970. Cook bergabung dengan fakultas Universitas Toronto, Ilmu Komputer dan Matematika pada tahun 1970 sebagai associate professor, di mana ia dipromosikan menjadi profesor pada tahun 1975 dan Profesor yang Terhormat pada tahun 1985. Stephen Cook dianggap sebagai salah satu nenek moyang teori kompleksitas komputasi. Selama PhD, Cook bekerja pada kompleksitas fungsi, terutama pada multiplikasi.

Dalam makalah seminalnya tahun 1971 "The Complexity of Theorem Proceding Procedures",  Cook meresmikan gagasan pengurangan waktu polinomial dan kelengkapan NP, dan membuktikan adanya masalah NP-complete oleh menunjukkan bahwa masalah kepuasan Boolean (biasanya dikenal sebagai SAT) adalah NP-complete.Teorema ini dibuktikan secara independen oleh Leonid Levin di Uni Soviet , dan dengan demikian diberi nama teorema Cook-Levin . Makalah ini juga merumuskan masalah paling terkenal dalam ilmu komputer, masalah P vs NP . Secara informal, pertanyaan "P vs. NP" menanyakan apakah setiap masalah optimasi yang jawabannya dapat diverifikasi secara efisien untuk kebenaran / optimalitas dapat diselesaikan secara optimal dengan algoritma yang efisien. Cook menduga bahwa ada masalah optimalisasi yang tidak dapat diselesaikan dengan algoritma efesien, yaitu, P tidak sama dengan NP. Dugaan ini telah menghasilkan banyak penelitian dalam teori kopleksitas komputasi, yang telah meningkatkan pemahaman tentang kesulitan inheren masalah komputasi dan apa yang dapat dihitung secara efisien. Namun, dugaan itu tetap terbuka dan merupakan salah satu dari tujuh Masalah Hadiah Milenium yang terkenal

Pada tahun 1982, Cook menerima penghargaan Turing atas kontribusinya pada teori kompleksitas. Kutipannya berbunyi:Untuk kemajuan pemahaman kita tentang kompleksitas perhitungan secara signifikan dan mendalam. Makalah seminalnya, The Complexity of Theorem Proving Procedures, dipresentasikan pada Simposium ACM SIGACT 1971 tentang Teori Komputasi, meletakkan dasar bagi teori Kelengkapan NP. Eksplorasi berikutnya dari batas-batas dan sifat kelas NP-lengkap masalah telah menjadi salah satu kegiatan penelitian yang paling aktif dan penting dalam ilmu komputer selama dekade terakhir.