استیون کوک
استیون آرتور کوک (به انگلیسی: Stephen Arthur Cook) (زاده ۱۴ دسامبر، ۱۹۳۹-بوفالو، نیویورک)، یک دانشمند آمریکایی علوم رایانه و یک ریاضیدان سرشناس است که سهم عمده‌ای در رشته‌های نظریه پیچیدگی محاسباتی و پیچیدگی اثبات داشته‌است. وی در حال حاضر یک استاد دانشگاه در بخش علوم کامپیوتر و ریاضیات دانشگاه تورنتو است.
| استیون آرتور کوک | |
|---|---|
| زادهٔ | ۱۴ دسامبر ۱۹۳۹ (۸۳ سال) بوفالو، نیویورک |
| ملیت | آمریکایی |
| محل تحصیل | دانشگاه هاروارد دانشگاه میشیگان |
| شناخته‌شده برای | ان‌پی کامل Proof complexity قضیه کوک لوین |
| جایزه(ها) | جایزه تورینگ (۱۹۸۲) |
| پیشینه علمی | |
| شاخه(ها) | علوم کامپیوتر |
| محل کار | دانشگاه کالیفرنیا، برکلی دانشگاه تورنتو |
| استاد راهنما | هائو وانگ |
| دانشجویان دکتری | والتر ساویتچ |
زندگی‌نامه
کوک در سال ۱۹۳۹ در بوفالو، نیویورک به دنیا آمد. پدرش یک شیمیدان بود و برای Union Carbide کار می‌کرد و در دانشگاه محلی بوفالو نیز تدریس می‌کرد.
وقتی کوک ۱۰ ساله شد، خانواده‌اش به مزرعه‌ای در کلارنس، نیویورک، نقل مکان کردند. در آنجا با ویلسون گریت بچ، مخترع ضربان ساز قابل کشت، آشنا شد. کوک، رابطه دوستی را با گریت بچ برقرار کرد و وقت زیادی را در کمک کردن به وی در لحیم کاری ترانزیستور صرف کرد. همین تجربه‌ها، دوره‌ای از مهندسی برق را برایش به ارمغان آورد.
در سال ۱۹۵۷ به دانشگاه میشیگان رفت. در آنجا او و دوستش برنامه‌ای برای تست کردن حدس گلدباخ نوشتند. تا وقتی که برنامه ادامه پیدا می‌کرد، بیانگر درستی حدس بود. در سال ۱۹۶۱ وی مدرک لیسانس خود را که بخش عمده‌اش را ریاضیات تشکیل می‌داد گرفت.
مدرک کارشناسی ارشد و دکترای خود را به ترتیب در سال‌های ۱۹۶۲ و ۱۹۶۶ از دانشگاه هاروارد دریافت کرد که هر دوی آن‌ها در ریاضیات بودند. هدف اولیهٔ کوک، تحقیقات در زمینه جبر بود، ولی در مقطع دکترا به طلسم علوم کابردی هائو ونگ، کسی که در منطق ریاضی و فلسفه تعلیم دیده بود، دچار شد. در این زمان، ونگ در حال کار روی اثبات خودکار قضیه، کشف خودکار اثبات‌ها به وسیلهٔ رایانه، بود.
کوک همچنین به کار مایکل رابین، به ویژه مقاله‌اش بر روی نظریه محاسبات پی برد. در ادامه، رابین تعدادی از لکچرها را به دست کوک رساند و در پایان، این اتفاقات کوک را به سمت مطالعه در زمینه محاسبات گزاره‌ای سوق داد.
او در سال ۱۹۶۶ به عنوان پروفسور دستیار به بخش ریاضیات دانشگاه کالیفرنیا، برکلی، پیوست و تا سال ۱۹۷۰، هنگامی که از انتصاب مجددش منع شد در آنجا ماند.
در یک سخنرانی که با سی‌امین سالگرد بخش EECS برکلی همراه بود، برنده جایزه تورینگ و پروفسور برکلی، ریچارد کارپ اظهار داشت: «سرافکندگی ابدی ماست که ما قادر نبودیم بخش ریاضی را ترغیب کنیم تا او را نگه دارند».
کوک در سال ۱۹۷۰ به عنوان یک پروفسور دستیار به هیئت علمی دانشگاه تورنتو، بخش‌های علوم کامپیوتر و ریاضیات پیوست که بعدها در آنجا، در سال ۱۹۷۵ به مقام پروفسور و در سال ۱۹۸۵ به مقام پروفسور دانشگاه ارتقا پیدا کرد.
او در سال ۱۹۶۸ ازدواج کرد. دو فرزند دارد که یکی از آن‌ها در حال تحصیل در مقطع دکترا در دانشگاه برکلی، رشته علوم رایانه است. کوک در حال حاضر به همراه همسر خود در تورنتو زندگی می‌کند. وی ویولن می‌نوازد و از قایقرانی لذت می‌برد.
پژوهش‌ها
کوک یکی از پدران نظریه پیچیدگی محاسباتی قلمداد می‌شود. در طول دوره دکترا، کوک در زمینه پیچیدگی توابع، به ویژه ضرب، کار کرد.
در اواسط دههٔ ۱۹۷۰ کوک تبادل بین زمان و حافظه در عملیات کامپیوتری را مورد بررسی قرار داد. وی قادر بود اثبات کند که هیچ روشی نمی‌تواند هم از نظر زمان کارا باشد و هم از نظر حافظه. سال بعد، در مقاله سال ۱۹۷۱ خود، «پیچیدگی رویه‌های اثبات قضیه»، مفاهیم کاهش چندجمله‌ای زمانی (که با کاهش کوک نیز شناخته شده‌است) و ان پی کامل بودن را رسمی‌کرد و وجود یک مسئله ان پی کامل را به وسیلهٔ نشان دادن اینکه مسئله ارضاپذیری بولی ان پی کامل است، اثبات کرد. این قضیه به‌طور مستقل توسط لئونید لوین در اتحاد جماهیر شوروی ثابت شد و به همین دلیل نام قضیه کوک-لوین را به خود گرفته‌است.
این مقاله، مشهورترین مسئله علوم کامپیوتر، یعنی مسئله برابری پی و ان‌پی را نیز رسمی‌کرده‌است. به بیان ساده‌تر مسئله برابری پی و ان‌پی به دنبال این است که آیا هر مسئله بهینه‌سازی که جواب‌هایش می‌توانند به‌طور مؤثری برای درستی/بهینگی مورد بررسی قرار گیرند، می‌تواند به‌طور بهینه‌ای با یک الگوریتم مؤثر و کارآمد حل شود یا خیر. با فراوانی این‌گونه مسائل بهینه‌سازی در زندگی روزمره، یک جواب مثبت به این سؤال، احتمالاً پیامدهای عملی و فلسفی عمیقی را دربر خواهد داشت.
کوک حدس می‌زند که مسائل بهینه‌سازی (با حل‌هایی که به آسانی بررسی شوند) وجود دارند که نمی‌توانند با الگوریتم‌های مؤثری حل شوند. به عبارت دیگر پی با ان پی برابر نیست. این حدس تعداد زیادی از تحقیقات در زمینه نظریه پیچیدگی محاسباتی را موجب شده‌است، که به‌طور قابل ملاحظه‌ای درک ما را از سختی ذاتی مسائل محاسباتی و اینکه چه چیزی می‌تواند به‌طور مؤثری محاسبه شود بهبود بخشیده‌است. در حال حاضر، این حدس، باز است و در میان ۷ مسئله ی یک میلیون دلاری قرار دارد.
در سال ۱۹۸۲ کوک جایزه معتبر تورینگ را به خاطر سهمش در نظریه پیچیدگی دریافت کرد. تقدیر از وی این‌گونه آغاز شد: «برای بالا بردن درک ما از پیچیدگی محاسبات با یک روش مهم و عمیق».
کوک بیش از ۱۰۰ مقاله در زمینه‌های علوم کامپیوتر نظری و پیچیدگی موازی منتشر کرده‌است. با این حال، هنوز هم به دلیل رسمی‌کردن ایده ان پی کامل بودن است که شناخته شده‌است.
جستارهای وابسته
منابع
- www.BookRegs.com
- www.cs.Toronto.edu