Stephen Arthur Cook (14 Desember 1939 - sekarang) merupakan seorang ilmuan komputer dan matematikawan Amerika - Kanada yang telah memberikan kontribusi besar pada bidang teori kompleksitas dan kompleksitas bukti . Dia adalah seorang profesor universitas di University of Toronto, Departemen Ilmu Komputer dan Departemen Matematika.
Perjalanan Hidup
.jpg)
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.[1] 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",[2] 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.
Karya
- On the Minimum Computation Time of Functions (1966) (Tesis)
- IP Address 76 Success Secrets - 76 Most Asked Questions on IP Address - What You Need to Know
- dll
Referensi
- ↑ Kapron, Bruce. "Stephen Arthur Cook". A. M. Turing Award. Diakses tanggal 23 Oktober 2018.
{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link) - ↑ A Personal View of Computer Science at Berkeley - Richard Karp
Pranala luar
- Home page of Stephen A. Cook
- ‘P versus NP’ and the Limits of Computation Diarsipkan 2016-03-04 di Wayback Machine. - Public lecture given by Stephen Cook at the University of Toronto
- Oral history interview with Stephen Cook at Charles Babbage Institute, University of Minnesota. Cook discussed his education at the University of Michigan and Harvard University and early work at the University of California, Berkeley, and his growing interest in problems of computational complexity. Cook recounted his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award.
- Stephen Cook di Mathematics Genealogy Project
- Stephen A. Cook pada DBLP Bibliography Server
