Stephen Cook
(ij³ª´Ù ÄÄÇ»ÅͰúÇÐÀÚ, ¼öÇÐÀÚ, 1939~)
¹öÆÈ·Î¿¡¼ ž 1962 ³â ÇϹٵ忡¼ ¹Ú»çÇÐÀ§¸¦ ¹Þ¾Ò´Ù. 1970 ³â ÀÌ·¡·Î Toronto ´ëÇÐ ±³¼ö·Î ÀÖ´Ù. ±×ÀÇ ÁÖ¿ä ¿¬±¸ºÐ¾ß´Â °è»êº¹ÀâµµÀÌ·Ð (Computational Complexity Theory), ÇÁ·Î±×·¡¹Ö ¾ð¾î Àǹ̷Ð, º´·Ä°è»ê, ³í¸®¿Í º¹ÀâµµÀÌ·Ð °£ÀÇ Á¢Á¡ ¿¬±¸µîÀÌ´Ù.
±×´Â °è»êÀÇ º¹Àâµµ¸¦ ÀÌÇØÇϱâ À§ÇÑ Áß¿äÇÏ°í ½É¿ÀÇÑ ¹æ¹ýÀ» Á¦½ÃÇÏ¿´´Ù. 1971 ACM SIGACT Symposium¿¡¼ ¹ßÇ¥µÈ ³í¹® "The Complexity of Theorem Proving Procedures," ¿¡¼´Â Theory of Computing, NP-Completeness ÀÌ·ÐÀ¸·Î À¯¸íÇÏ´Ù. NP-complete ¹®Á¦ ºÎ·ùÀÇ °æ°è¼±°ú ¼º°Ý¿¡ ´ëÇÑ Å½±¸´Â ÃÖ±Ù ÄÄÇ»ÅͰúÇп¡¼ °¡Àå Áß¿äÇÑ ¿¬±¸È°µ¿ÁßÀÇ Çϳª·Î ¾Ë·ÁÁ®ÀÖ´Ù. 1982 ³â¿¡ Alan Turing »óÀ» ¼ö»óÇÏ¿´´Ù.
½ºÆ¼ºì Äî°ú ·¹¿À´Ïµå ·¹ºó : Dennis Shasha : .... ¼øÈ¸ÆÇ¸Å¿ø ¹®Á¦ (Travelling Salesman Problem) ¿¡¼ ...... ¸¸ÀÏ 100 °³ÀÇ µµ½Ã°¡ ÀÖ´Ù¸é 100 ÀÇ °è½Â¿¡ ÇØ´çÇÏ´Â ¿©Çà ¹æ¹ýµéÀ» Æò°¡ÇØ¾ß ÇÕ´Ï´Ù. ¾î¶°ÇÑ ÄÄÇ»Å͵µ 100 ÀÇ °è½Â¸¸ÅÀÇ ¿©Çà ¹æ¹ýÀ» ½ÃµµÇØ º¼ ¼ö´Â ¾øÀ» °ÍÀÔ´Ï´Ù. »ç¶÷µéÀÌ ±×°ÍÀ» ÀÌÇØÇϱâ´Â ¾î·ÆÁö¿ä. ¸î °¡Áö °£´ÜÇÑ °è»êÀ» ÇØ º¸¸é, ¸¸ÀÏ ´ç½ÅÀÌ Å¾ç°è¿¡¼ °¢°¢ÀÇ È¸Àü¼ö¿¡ ºñÇÒ ¸¸ÇÑ ºóµµ·Î ±×°Í¿¡ ÀÛ¿ëÇÏ´Â ¸ðµç ÀüÀÚµéÀ» °¡Áö°í ÀÖÀ» °æ¿ì, ±×°ÍÀ» ã´Â µ¥¿¡´Â žçÀÌ ´Ù Ÿ ¹ö¸± ¶§±îÁö ½Ã°£ÀÌ °É¸± °ÍÀ̶õ »ç½ÇÀ» ±ú´ÞÀ» ¼ö ÀÖ½À´Ï´Ù. ¿ì¸®°¡ ÀÌÇØÇØ¾ß ÇÒ ±âº»ÀûÀÎ ¿äÁ¡Àº ½ÇÁ¦·Î ½ÇÇà¿¡ ¿Å±æ ¼ö ¾ø´Â ÀϵéÀÌ Á¸ÀçÇÑ´Ù´Â »ç½ÇÀÔ´Ï´Ù.
¼±¸ °è»ê ÀÌ·ÐÀÇ ÀüÅë¿¡¼ °è»êÀÇ ³À̵µ¶ó´Â °³³äÀº ³í¸®Çаú ¾Ù·± Æ©¸µÀÌ Á¦½ÃÇÑ '°è»ê ºÒ°¡´É¼º' ÀÇ ¿¬±¸ °á°ú¿¡ »Ñ¸®¸¦ µÎ°í ÀÖ´Ù. ¸¶ÀÌŬ ¶óºóÀº 1959 ³â °è»ê °¡´ÉÇÑ ¹®Á¦µéÀÇ °íÀ¯ÇÑ ³À̵µ¶ó´Â °³³äÀ» ÃÖÃÊ·Î °ø½ÄÈÇÏ¿´´Ù. 1971 ³â ºñ´ÙÇ×½Ä ¿ÏÀü ¹®Á¦¸¦ Á¤ÀÇÇÏ¸é¼ ½ºÆ¼ºì ÄîÀº À̰°Àº ÀüÅëÀ» µû¸£°í ÀÖ¾ú´Ù.
'ºñ´ÙÇ×½Ä ¿ÏÀü ¹®Á¦°¡ öÀúÇÑ Á¶»ç¸¦ ÇÊ¿ä·Î Çϴ°¡ ¾Æ´Ï¸é ÇÊ¿ä·ÎÇÏÁö ¾Ê´Â°¡?' ¶ó´Â ¹®Á¦ÀÌ´Ù. ±×°ÍÀ» ´Ù¸¥ ½ÄÀ¸·Î Ç¥ÇöÇÏ¸é ´ÙÀ½°ú °°´Ù. Áï, ¼¼ÀÏÁî¸ÇÀÇ ¿©Çà ¹®Á¦¿Í °°Àº ¹®Á¦µé¿¡ ´ëÇØ °¡´ÉÇÑ °æ·Îµé °¡¿îµ¥ ¿À·ÎÁö ¾î¶² ÀÛÀº ºÎºÐ¸¸À» °ËÅäÇÏ¸é¼ ±× ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Â ¾Ë°í¸®ÁòÀÌ ÄÄÇ»ÅÍ °úÇÐÀÇ ¿ª»ç¸¦ º¯È½Ãų °ÍÀ̶õ À̾߱âÀÌ´Ù. ..........
NP=P ¸¦ Áõ¸íÇÒ ¼ö ÀÖÁö ¾ÊÀ»±î? ´Ù½Ã ¸»ÇØ, ´ÙÇ×½Ä ½Ã°£ ³»¿¡ ±× ÇØ¹ýÀÌ 'ÇØ°á' µÉ ¼ö ÀÖ´Â ¹®Á¦°¡ ´ÙÇ×½Ä ½Ã°£ ³»¿¡ '°ËÅä' µÉ ¼öµµ ÀÖÀ»±î? (±×¸² 2 ÂüÁ¶)
±×¸² 2 ¾î¶² ¹®Á¦°¡ ¾î´À Á¤µµÀÇ ½Ã°£ ³»¿¡ ÇØ°áµÉ ¼ö ÀÖ´Ù¸é, ±×°ÍÀÇ ÇØ¹ýÀº ±× ½Ã°£ ³»¿¡ °ËÅäµÉ ¼ö ÀÖ´Ù. µû¶ó¼, P ´Â NP ³»¿¡ Æ÷ÇԵȴÙ. ÄÄÇ»ÅÍ °úÇп¡¼ ¾ÆÁ÷ ¹ÌÇØ°á »óÅÂÀÎ À̷лóÀÇ ÇÑ °¡Áö Å« ¹®Á¦´Â, NP-¿ÏÀü¿¡ ¼ÓÇÏ´Â ¼öõ °¡Áö Áß¿äÇÑ ¹®Á¦µéÀÌ ½ÇÁ¦·Î ´ÙÇ×½Ä ½Ã°£ ³»¿¡ ÇØ°áµÉ ¼ö ÀÖ´ÂÁö ¾Æ´Ï¸é Áö¼ö ½Ã°£À» ÇÊ¿ä·Î ÇÏ´ÂÁö ¿©ºÎÀÌ´Ù. ´Ù½Ã ¸»ÇØ, P °¡ NP ¿Í ÀÏÄ¡Çϴ°¡ÀÇ ¹®Á¦ÀÎ °ÍÀÌ´Ù. |
Äî |
ÀÌ ºÐ¾ßÀÇ ¼öÇÐÀÌ Ã³ÇØ ÀÖ´Â ½½Ç »óȲÀº ¿ì¸®°¡ À̰͵éÀ» Áõ¸íÇÒ ¼ö ¾ø´Ù´Â °ÍÀÔ´Ï´Ù. ¿ì¸®´Â P °¡ NP ¿Í ÀÏÄ¡ÇÏÁö ¾Ê´Â´Ù´Â °ÍÀ» Áõ¸íÇÒ ¼ö°¡ ¾ø½À´Ï´Ù. µû¶ó¼, °á±¹¿£ ´©±º°¡°¡ NP-¿ÏÀü ¹®Á¦¸¦ ´ÙÇ×½Ä ½Ã°£ ³»¿¡ ÇØ°áÇÒ ¾î¶² ¸íÄèÇÑ º´·Ä ¾Ë°í¸®ÁòÀ» °í¾ÈÇØ ³¾ ¼ö ÀÖÀ» °ÍÀÔ´Ï´Ù. |
ÀÌ¿Í °°Àº »ç·Ê¿¡¼ ¾î¶² ÁøÀüÀÌ ÀÖ´ÂÁö¸¦ ¸»Çϱâ´Â ¾î·Æ½À´Ï´Ù. ±×°ÍÀº °ð ÀÓ¹ÚÇÑ °ÍÀÌ ¾Æ´Ï¶ó, ´ÜÁö ºÎºÐÀûÀÎ °á°úµéÀÌ ÀÖÀ» »ÓÀÔ´Ï´Ù. »ç¶÷µéÀº °¢±â ´Ù¸¥ ¼ö¸¹Àº ¿µ¿ª¿¡¼ ±× ¹®Á¦¸¦ °ø·«Çϰí ÀÖ½À´Ï´Ù. ±×¸®°í ¾îÂîµÇ¾úµç P = NP °¡ µÇ´Â °ÍÀº °¡´ÉÇÕ´Ï´Ù.
term :
Stephen Cook °è»êº¹ÀâµµÀÌ·Ð (Computational Complexity Theory) NP-complete ¼øÈ¸ÆÇ¸Å¿ø ¹®Á¦ (Traveling Salesman Problem) Æ©¸µ »ó(Turing Award) Leonid Levin
site :
Stephen Cook's home page : Toronto ´ëÇÐ ÄÄÇ»ÅͰúÇаú, Biography
video :
The Ultimate Limits of Computers : Techfest 2013 Bombay : Stephen Cook, 2013/05/06
Interview with Prof. Stephen A. Cook, 2012 Winner of NSERC's Herzberg Medal : Stephen Cook, 2013/02/27
NSERC Presents 2 Minutes with Stephen Cook : NSERCTube : Stephen Cook, 2013/02/27