Computational Complexity Theory
¼±¸ °è»ê ÀÌ·ÐÀÇ ÀüÅë¿¡¼ °è»êÀÇ º¹Àâµµ¶ó´Â °³³äÀº ³í¸®Çаú Alan Turing ÀÌ Á¦½ÃÇÑ '°è»ê °¡´É¼º' ÀÇ ¿¬±¸ °á°ú¿¡ »Ñ¸®¸¦ µÎ°í ÀÖ´Ù
º¹Àâµµ ÀÌ·Ð (Complexity Theory) Àº ÁÖ¾îÁø ¹®Á¦¸¦ Ç®±âÀ§ÇØ °è»ê°úÁ¤¿¡ ÇÊ¿ä·Î ÇÏ´Â ÀÚ¿øÀ» ´Ù·ç´Â °è»êÀÌ·Ð (Theory of Computation) ÀÇ ÀϺÎÀÌ´Ù. °¡Àå ÈçÇÑ ÀÚ¿øÀº ½Ã°£ (¹®Á¦¸¦ Ç®±âÀ§ÇØ ¾ó¸¶³ª ¸¹Àº ´Ü°è¸¦ °ÅÄ¡°Ô µÇ´Â°¡) ¿Í °ø°£ (¹®Á¦¸¦ Ç®±âÀ§ÇØ ¾ó¸¶³ª ¸¹Àº ¸Þ¸ð¸®¸¦ ÇÊ¿ä·Î Çϴ°¡) ÀÌ´Ù. À̿ܿ¡µµ ¹®Á¦¸¦ º´·ÄÀûÀ¸·Î Ç®±âÀ§ÇØ ¾ó¸¶³ª ¸¹Àº º´·Ä ÇÁ·Î¼¼¼°¡ ÇÊ¿äÇѰ¡ ¿Í °°Àº ´Ù¸¥ ÀÚ¿øµéÀÌ °í·ÁµÉ ¼ö ÀÖ´Ù. Complexity theory ´Â ÇÊ¿äÇÑ ÀÚ¿ø°ú´Â ¹«°üÇÏ°Ô ¾î¶² ¹®Á¦¸¦ Ç® ¼ö ÀÖ´ÂÁö ¾ø´ÂÁö¸¦ ´Ù·ç´Â °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory) °ú´Â ´Ù¸£´Ù.
´Ü ÇϳªÀÇ "¹®Á¦" ´Â °ü·Ã Áú¹®µéÀÇ Àüü ÁýÇÕÀ̸ç, À̶§ Áú¹®Àº À¯ÇÑ ±æÀÌÀÇ ¹®ÀÚ¿ÀÌ´Ù. ¿¹¸¦µé¸é ÀμöºÐÇØ (factorize) ¹®Á¦¿¡¼, ÀÌÁø¹ýÀ¸·Î ¾²¿©Áø Á¤¼ö°¡ ÁÖ¾îÁö°í, ±× ¼öÀÇ ¼ÒÀμö¸¦ ÀüºÎ ¹ÝȯÇÑ´Ù. ¾î¶² Ưº°ÇÑ Áú¹®À» instance ¶ó°í ºÎ¸¥´Ù. ¿¹¸¦µé¸é "15 ÀÇ ÀμöµéÀ» ±¸Çضó" ÇÏ´Â °ÍÀº ÀμöºÐÇØ ¹®Á¦ÀÇ ÇÑ instance ÀÌ´Ù.
½Ã°£ º¹Àâµµ (time complexity) ´Â °¡Àå È¿À²ÀûÀÎ (º¸Åë bit ·Î¼ ÃøÁ¤µÈ´Ù) ¾Ë°í¸®ÁòÀ» »ç¿ëÇØ¼ ÇÑ ¹®Á¦ÀÇ instance ¸¦ Ǫ´Âµ¥ °É¸®´Â ´Ü°èÀÇ ¼ö¸¦ ÀǹÌÇÑ´Ù. Áï n bit ±æÀÌÀÇ instance °¡ n2 ´Ü°è ³»¿¡ Ç®¸± ¼ö ÀÖ´Ù¸é ±× ¹®Á¦´Â n2 ÀÇ ½Ã°£ º¹Àâµµ¸¦ °¡Áø´Ù°í ¸»ÇÑ´Ù. ¹°·Ð ´Ü°èÀÇ Á¤È®ÇÑ ¼ö´Â »ç¿ëµÇ´Â ±â°è³ª ¾ð¾î¿¡ ÀÇÁ¸ÇÒ °ÍÀÌ´Ù. ±×·± ¹®Á¦¸¦ ÇÇÇϱâ À§ÇØ º¸Åë Big O notation À» »ç¿ëÇÑ´Ù. ¸¸ÀÏ ¾î¶² ¹®Á¦°¡ ÀϹÝÀûÀÎ ÄÄÇ»ÅÍ¿¡¼ ½Ã°£ º¹Àâµµ O(n2) ¸¦ °¡Áø´Ù¸é, ´ëºÎºÐÀÇ ´Ù¸¥ ÄÄÇ»ÅÍ¿¡¼µµ º¹Àâµµ O(n2) ¸¦ °¡Áú °ÍÀ̹ǷÎ, ÀÌ·¯ÇÑ notation Àº Ưº°ÇÑ ÄÄÇ»ÅÍ¿¡ ±¸¾Ö¹ÞÁö ¾Ê°í ÀϹÝÈ ÇÒ ¼ö ÀÖ°Ô ÇØÁØ´Ù.
¿¹) ÀâÃÊ ±ð±â´Â µÎ¹èÀÇ ¸éÀûÀ» ±ð´Âµ¥´Â µÎ¹èÀÇ ½Ã°£ÀÌ °É¸®±â ¶§¹®¿¡ ¼±Çü (linear) º¹Àâµµ¸¦ °¡Áø´Ù. ±×·¯³ª »çÀü¿¡¼ ¾î¶² °ÍÀ» ãÀ» ¶§, µÎ¹è Å©±âÀÇ »çÀüÀÇ °æ¿ì¿¡ »çÀüÀ» Çѹø ÀÌ»ó ´õ ¿¾îºÁ¾ß Çϱ⠶§¹®¿¡ Áö¼ö (logarithmic) º¹Àâµµ¸¦ °¡Áø´Ù (¿¹¸¦µé¾î Á¤È®ÇÏ°Ô Áß°£À̶ó¸é ±× ¹®Á¦´Â ¹ÝÀ¸·Î °¨¼ÒÇÑ´Ù)
º¹Àâµµ ÀÌ·ÐÀ¸·Î À¯¸íÇÑ Àι°Àº Juris Hartmanis, Richard Stearns, Stephen Cook, Richard Karp, Leonid Levin µîÀÌ ÀÖ´Ù. ±×µéÀº ´ëºÎºÐ Alan Turing »ó À» ¼ö»óÇß´Ù. Cook ´Â 1971 ³â¿¡ ³í¹® "The Complexity of Theorem Proving Procedures"¿¡¼ NP-completeness ¸¦ Á¤ÀÇÇϰí boolean satisfiability problem ´Â NP-complete ÀÌ´Ù ¶ó´Â Áõ¸íÀ» ÇÏ¿´´Ù. ±× ³í¹®À¸·Î P ¿Í NP º¹Àâµµ°¡ °°Àº °ÍÀÎÁö ¾Æ´ÑÁö (Áï NP = P ÀÎÁö) ÇÏ´Â ÄÄÇ»ÅÍ °úÇÐÀÇ À§´ëÇÑ ¹ÌÇØ°á ¹®Á¦¸¦ ¿¾î³õ¾Ò°í, ±×°Í¿¡ ´ëÇÑ ´ë´äÀ» ¹ß°ßÇÏÁö ¸øÇϰí ÀÖ´Ù.
Áï 'NP-complete °¡ öÀúÇÑ Á¶»ç¸¦ ÇÊ¿ä·Î Çϴ°¡ ¾Æ´Ï¸é ÇÊ¿ä·ÎÇÏÁö ¾Ê´Â°¡?' ¶ó´Â ¹®Á¦ÀÌ´Ù. ±×°ÍÀ» ´Ù¸¥ ½ÄÀ¸·Î Ç¥ÇöÇÏ¸é ´ÙÀ½°ú °°´Ù. Áï, ¼¼ÀÏÁî¸ÇÀÇ ¿©Çà ¹®Á¦¿Í °°Àº ¹®Á¦µé¿¡ ´ëÇØ °¡´ÉÇÑ °æ·Îµé °¡¿îµ¥ ¿À·ÎÁö ¾î¶² ÀÛÀº ºÎºÐ¸¸À» °ËÅäÇÏ¸é¼ ±× ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Â ¾Ë°í¸®Áò ÀÌ ÄÄÇ»ÅÍ °úÇÐÀÇ ¿ª»ç¸¦ º¯È½Ãų °ÍÀ̶õ À̾߱âÀÌ´Ù.
Juris Hartmanis ¿Í Richard Stearns Àº °è»ê º¹Àâµµ ÀÌ·Ð ºÐ¾ßÀÇ ±âÃʸ¦ ³õÀº ³í¹® On the computational complexity of algorithms (1965) À» ¹ßÇ¥Çß´Ù. ........... (Wikipedia : Computational Complexity Theory)
º¹À⼺ À̷п¡¼´Â ¾Ë°í¸®ÁòÀÇ ¼Óµµ°¡ ´ÙÇ×½ÄÀ¸·Î Ç¥ÇöµÇ´Â ¹®Á¦µéÀ» ¹¾î¼ 'P' ¶ó°í ºÎ¸£°í, ´ÙÇ×½ÄÀ¸·Î Ç¥ÇöµÉ ¼ö ÀÖ´ÂÁö ¿©ºÎ°¡ ¾Ë·ÁÁöÁö ¾ÊÀº ¹®Á¦µéÀ» ¹¾î¼ 'NP' ¶ó°í ºÎ¸¥´Ù. ¿©±â¼ P ´Â Polynomial (´ÙÇ×½Ä) ÀÇ ¸Ó¸® ±ÛÀÚ°í, NP ´Â nondeterministic polynomial (ºñ°áÁ¤¼º ´ÙÇ×½Ä) ÀÇ ¸Ó¸® ±ÛÀÚ¸¦ ÀǹÌÇÑ´Ù. À̶§ NP °¡ non-polynomial (ºñ´ÙÇ×½Ä) À» ÀǹÌÇÏÁö ¾Ê´Â´Ù´Â »ç½Ç¿¡ À¯ÀÇÇÒ Çʿ䰡 ÀÖ´Ù. ´ÙÇ×½ÄÀÌ ¾Æ´Ï¶ó´Â »ç½Ç°ú ´ÙÇ×½ÄÀ¸·Î Ç¥ÇöµÇ´ÂÁö ¿©ºÎ°¡ ¾ÆÁ÷ ¾Ë·ÁÁöÁö ¾Ê¾Ò´Ù´Â »ç½Ç »çÀÌ¿¡´Â ¾öû³ Â÷À̰¡ Á¸ÀçÇϱ⠶§¹®ÀÌ´Ù. ´ÙÇ×½ÄÀ¸·Î Ç¥ÇöµÇ´Â ¾Ë°í¸®ÁòÀº ¿À´Ã³¯ÀÇ ÄÄÇ»ÅͰ¡ Àû´çÇÑ ½Ã°£³»¿¡ ÇØ°áÇÒ ¼ö ÀÖ´Â ¹®Á¦±â ¶§¹®¿¡ P ¿¡ ¼ÓÇÑ ¹®Á¦µéÀº '½¬¿î' ¹®Á¦µéÀ̰í, NP ´Â ±×¿Í ¹Ý´ë·Î '¾î·Á¿î' ¹®Á¦¸¦ ÀǹÌÇÑ´Ù.
º¹À⼺ ¹®Á¦¸¦ ¿¬±¸ÇÏ´Â ÇÐÀڵ鿡°Ô °¡Àå ¾î·Á¿î Áú¹®ÁßÀÇ Çϳª´Â ¹Ù·Î "NP ¿¡ ¼ÓÇÏ´Â ¹®Á¦µéÀÌ ±Ã±ØÀûÀ¸·Î´Â ¸ðµÎ ´ÙÇ×½Ä, Áï ½¬¿î ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇØ¼ ÇØ°áµÉ ¼ö ÀÖÀ»±î?" ¶ó´Â Áú¹®ÀÌ´Ù. ¸¸¾à ±×·¸´Ù¸é NP ¿¡ ¼ÓÇÑ ¹®Á¦³ª P ¿¡ ¼ÓÇÑ ¹®Á¦°¡ ¸ðµÎ Á¾±¹¿¡´Â ´ÙÇ×½ÄÀ¸·Î Ç¥ÇöµÇ±â ¶§¹®¿¡ 'P = NP' ¶ó´Â µî½ÄÀÌ ¼º¸³ÇÏ°Ô µÉ °ÍÀÌ´Ù. ÇÏÁö¸¸ NP ¿¡ ¼ÓÇÏ´Â ¹®Á¦°¡ ¸ðµÎ ´ÙÇ×½ÄÀ¸·Î ÇØ°áµÉ ¼ö ÀÖÀ»Áö ¿©ºÎ¸¦ ÆÄ¾ÇÇϰųª Áõ¸íÇÏ´Â °ÍÀÌ ³Ê¹«³ª ¾î·Æ±â ¶§¹®¿¡ ÀÌ µî½ÄÀº ¾ÆÁ÷µµ ¿ÏÀüÇÏ°Ô ÀÔÁõµÇÁö ¾ÊÀº ¾î·Á¿î ¸íÁ¦ ÁßÀÇ Çϳª·Î ÅëÇϰí ÀÖ´Ù.
ÇÑÆí 'NP-hard' ¶ó°í ºÒ¸®´Â ¹®Á¦µéÀº ¼¼ÀÏÁî¸ÇÀÇ ¿©Çà ¹®Á¦Ã³·³ ¸ðµç °æ¿ìÀÇ ¼ö¸¦ ÀüºÎ È®ÀÎÇØº¸´Â ¹æ¹ý À̿ܿ¡´Â Á¤È®ÇÑ ´äÀ» ±¸ÇÒ ¼ö ÀÖ´Â »ÏÁ·ÇÑ ¼ö°¡ ¾ø´Â ¹®Á¦µéÀ» ¶æÇÑ´Ù. ¾î¶² ¹®Á¦°¡ NP ¿¡ ¼ÓÇϸé¼, Áï ´ÙÇ×½ÄÀ¸·Î Ç¥ÇöµÉ ¼ö ÀÖ´ÂÁö ¿©ºÎ°¡ ¾Ë·ÁÁöÁö ¾Ê¾ÒÀ¸¸é¼ µ¿½Ã¿¡ NP-hard ¿¡ ¼ÓÇÑ´Ù¸é ...... ±× ¹®Á¦´Â 'NP ¿ÏÀü ¹®Á¦ (NP-complete)' ¶ó°í ºÎ¸¥´Ù. .......
ÀÌ·¯ÇÑ NP ¿ÏÀü ¹®Á¦¿¡ ¼ÓÇÏ´Â ¹®Á¦´Â ¸¹´Ù. ºñ¹Ð¹øÈ£¸¦ ±ú¶ß¸®±â À§ÇÑ ÇØÅ· °úÁ¤µµ ¸»ÇÏÀÚ¸é ÀÌ·¯ÇÑ NP ¿ÏÀü ¹®Á¦¿¡ ¼ÓÇÑ´Ù°í º¼ ¼ö ÀÖ´Ù. ºñ¹Ð¹øÈ£¸¦ ã¾Æ³»±â À§ÇÑ ¾Ë°í¸®ÁòÀ¸·Î´Â ¼¼ÀÏÁî¸ÇÀÇ ¿©Çà ¹®Á¦¿¡¼ ó·³ ¹®ÀÚ¸¦ Çϳª¾¿ ´ëÀÔÇØ º¸´Â °Í ¸»°í´Â ´Ù¸¥ »ÏÁ·ÇÑ ¹æ¹ýÀÌ ¾ø±â ¶§¹®ÀÌ´Ù ........... (ÀÓ¹éÁØ 2003)
term :
°è»ê º¹Àâµµ ÀÌ·Ð (Computational Complexity Theory) °è»êÀÌ·Ð (Theory of Computation) ´ÙÇ׽İú ºñ°áÁ¤´ÙÇ×½Ä (P and NP) ºñ°áÁ¤ ³ÇØ (NP-hard) ºñ°áÁ¤ ¿ÏÀü (NP-complete)
site :
Wikipedia : Computational Complexity Theory
Computational Complexity of Games & Puzzles : David Eppstein
paper :
video :
P vs. NP and the Computational Complexity Zoo : 2014/08/26
The Turing Computational Model : Juris Hartmanis, Richard Stearns, Stephen Cook, William Kahan : 2013/01/18
Computational Complexity : MIT : Erik Demaine, 2013/01/14