์ฝ˜ํ…์ธ  ๋Œ€ํ‘œ ์ด๋ฏธ์ง€ - ๐Ÿงฉ ๊ณ„์‚ฐ ๋ณต์žก๋„ ์ด๋ก ๊ณผ P vs NP ๋ฌธ์ œ๋กœ ์ฝ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํšจ์œจ์„ฑ ๋ถ„์„

๐Ÿงฉ ๊ณ„์‚ฐ ๋ณต์žก๋„ ์ด๋ก ๊ณผ P vs NP ๋ฌธ์ œ๋กœ ์ฝ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํšจ์œจ์„ฑ ๋ถ„์„

"์ •๋‹ต์„ ํ™•์ธํ•˜๋Š” ๊ฒŒ ์‰ฌ์šฐ๋ฉด, ์ •๋‹ต์„ ์ฐพ๋Š” ๊ฒƒ๋„ ์‰ฌ์šธ๊นŒ?" ์ด ํ•œ ์ค„์งœ๋ฆฌ ์งˆ๋ฌธ์— 100๋งŒ ๋‹ฌ๋Ÿฌ๊ฐ€ ๊ฑธ๋ ค ์žˆ๋‹ค๋Š” ๊ฑฐ, ์•Œ๊ณ  ์žˆ์—ˆ์–ด? ์˜ค๋Š˜์€ ์นœ๊ตฌ๋ž‘ ์นดํŽ˜์—์„œ ์ˆ˜๋‹ค ๋–จ๋“ฏ์ด, ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ ๊ฐ€์žฅ ์œ ๋ช…ํ•œ ๋ฏธํ•ด๊ฒฐ ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ๊ฐ™์ด ๋”ฐ๋ผ๊ฐ€ ๋ณด์ž.

P โ‰  NP๋ผ๊ณ  ๊ฐ€์ •ํ•œ ์„ธ๊ณ„ ์ง€๋„ P ์ •๋ ฌ ยท ์ตœ๋‹จ๊ฒฝ๋กœ ์†Œ์ˆ˜ ํŒ์ • NP ๋‹ต์„ ๋น ๋ฅด๊ฒŒ ๊ฒ€์ฆ ๊ฐ€๋Šฅ NP- ์™„์ „ SAT TSP NP-๋‚œํ•ด ์ •์ง€ ๋ฌธ์ œ (๊ฒ€์ฆ๋„ ๋ถˆ๊ฐ€) ? ์ดˆ๋ก ์›์ด ํŒŒ๋ž€ ์›์„ ๋‹ค ๋ฎ์œผ๋ฉด P = NP ๋ณด๋ผ์ƒ‰ ๊ฒน์นจ = NP ์•ˆ์— ์žˆ์œผ๋ฉด์„œ ๊ฐ€์žฅ ์–ด๋ ค์šด ๋ฌธ์ œ๋“ค

๋ณต์žก๋„ ํด๋ž˜์Šค์˜ ํฌํ•จ ๊ด€๊ณ„ (P โ‰  NP ๊ฐ€์ •. P = NP๋ผ๋ฉด PยทNPยทNP-์™„์ „์ด ํ•œ ๋ฉ์–ด๋ฆฌ๋กœ ํ•ฉ์ณ์ง)

๐Ÿข 1. ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด "๋น ๋ฅด๋‹ค"๋Š” ๊ฑด ๋Œ€์ฒด ๋ฌด์Šจ ๋œป์ผ๊นŒ

์นœ๊ตฌ์•ผ, ์ผ๋‹จ ์•„์ฃผ ํ˜„์‹ค์ ์ธ ์งˆ๋ฌธ๋ถ€ํ„ฐ ๋˜์ ธ๋ณผ๊ฒŒ. ์–ด๋–ค ํ”„๋กœ๊ทธ๋žจ์ด "๋น ๋ฅด๋‹ค"๊ณ  ๋งํ•  ๋•Œ, ์šฐ๋ฆฌ๋Š” ๋ณดํ†ต ์ดˆ์‹œ๊ณ„๋ฅผ ๋– ์˜ฌ๋ฆฌ์ž–์•„. "์ด ์ฝ”๋“œ๋Š” 0.3์ดˆ ๋งŒ์— ๋๋‚˜!" ์ด๋Ÿฐ ์‹์œผ๋กœ. ๊ทผ๋ฐ ์ด ์ธก์ •์—๋Š” ํ•จ์ •์ด ์žˆ์–ด. ๋˜‘๊ฐ™์€ ์ฝ”๋“œ๋ผ๋„ ์ตœ์‹  ๋…ธํŠธ๋ถ์—์„œ ๋Œ๋ฆฌ๋ฉด 0.3์ดˆ, 10๋…„ ๋œ ์ปดํ“จํ„ฐ์—์„œ ๋Œ๋ฆฌ๋ฉด 3์ดˆ๊ฐ€ ๊ฑธ๋ฆด ์ˆ˜ ์žˆ๊ฑฐ๋“ . ๊ทธ๋Ÿฌ๋ฉด ์ฝ”๋“œ๊ฐ€ ๋น ๋ฅธ ๊ฑธ๊นŒ, ์ปดํ“จํ„ฐ๊ฐ€ ๋น ๋ฅธ ๊ฑธ๊นŒ?

๊ทธ๋ž˜์„œ ์ปดํ“จํ„ฐ ๊ณผํ•™์ž๋“ค์€ ๊ธฐ๊ณ„ ์„ฑ๋Šฅ๊ณผ ๋ฌด๊ด€ํ•œ ๊ธฐ์ค€์„ ๋งŒ๋“ค์—ˆ์–ด. ๋ฐ”๋กœ "์ž…๋ ฅ ํฌ๊ธฐ๊ฐ€ ์ปค์งˆ ๋•Œ ํ•„์š”ํ•œ ์—ฐ์‚ฐ ํšŸ์ˆ˜๊ฐ€ ์–ด๋–ค ์†๋„๋กœ ๋Š˜์–ด๋‚˜๋Š”๊ฐ€"์•ผ. ๋ฐ์ดํ„ฐ๊ฐ€ 10๊ฐœ์ผ ๋•Œ์™€ 100๋งŒ ๊ฐœ์ผ ๋•Œ๋ฅผ ๋น„๊ตํ•ด์„œ, ์ฆ๊ฐ€ ๊ณก์„ ์˜ "๋ชจ์–‘"๋งŒ ๋ณด๋Š” ๊ฑฐ์ง€. ์ด๊ฒŒ ๊ณ„์‚ฐ ๋ณต์žก๋„ ์ด๋ก ์˜ ์ถœ๋ฐœ์ ์ด์•ผ.

๐Ÿ“ ๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•: ์ฆ๊ฐ€ ์†๋„์— ๋ถ™์ด๋Š” ์ด๋ฆ„ํ‘œ

์ฆ๊ฐ€ ๊ณก์„ ์˜ ๋ชจ์–‘์„ ํ‘œํ˜„ํ•˜๋Š” ์–ธ์–ด๊ฐ€ ๋ฐ”๋กœ ๋น…์˜ค(Big-O) ํ‘œ๊ธฐ๋ฒ•์ด์•ผ. ์ •ํ™•ํ•œ ์ •์˜๋Š” ์ด๋ž˜.
ํ•จ์ˆ˜ f(n)์— ๋Œ€ํ•ด, ์–ด๋–ค ์ƒ์ˆ˜ c > 0๊ณผ nโ‚€๊ฐ€ ์กด์žฌํ•ด์„œ ๋ชจ๋“  n โ‰ฅ nโ‚€์— ๋Œ€ํ•ด f(n) โ‰ค cยทg(n)์ด๋ฉด f(n) = O(g(n))์ด๋ผ๊ณ  ์“ด๋‹ค.

๋ง๋กœ ํ’€๋ฉด "์ถฉ๋ถ„ํžˆ ํฐ ์ž…๋ ฅ์—์„œ, ์ƒ์ˆ˜๋ฐฐ๋ฅผ ๋ฌด์‹œํ•˜๋ฉด f๋Š” g๋ณด๋‹ค ๋นจ๋ฆฌ ์ž๋ผ์ง€ ์•Š๋Š”๋‹ค"๋Š” ๋œป์ด์•ผ. ์˜ˆ๋ฅผ ๋“ค์–ด ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ •ํ™•ํžˆ 3nยฒ + 5n + 7๋ฒˆ ์—ฐ์‚ฐํ•œ๋‹ค๋ฉด, n์ด ์ปค์งˆ์ˆ˜๋ก 3nยฒ์ด ์••๋„์ ์ด ๋˜๊ณ  ์ƒ์ˆ˜ 3๋„ ๊ธฐ๊ณ„ ์ฐจ์ด ์ˆ˜์ค€์ด๋‹ˆ ๊ทธ๋ƒฅ O(nยฒ)์ด๋ผ๊ณ  ๋ถ€๋ฅด๋Š” ๊ฑฐ์ง€.

๋น…์˜ค์˜ ์นœ์ฒ™๋“ค๋„ ์•Œ์•„๋‘๋ฉด ์ข‹์•„.

O (๋น…์˜ค) โ€” ์ƒํ•œ
"์•„๋ฌด๋ฆฌ ๋‚˜๋น ๋„ ์ด๊ฒƒ๋ณด๋‹ค๋Š” ์•ˆ ๋А๋ ค." ์ตœ์•…์˜ ๊ฒฝ์šฐ๋ฅผ ๋ณด์žฅํ•  ๋•Œ ์ฃผ๋กœ ์จ.
ฮฉ (๋น…์˜ค๋ฉ”๊ฐ€) โ€” ํ•˜ํ•œ
"์ตœ์†Œํ•œ ์ด๋งŒํผ์€ ๊ฑธ๋ ค." ์˜ˆ๋ฅผ ๋“ค์–ด ๋น„๊ต ๊ธฐ๋ฐ˜ ์ •๋ ฌ์€ ฮฉ(n log n)์ด ํ•„์š”ํ•˜๋‹ค๋Š” ๊ฒŒ ์ฆ๋ช…๋ผ ์žˆ์–ด.
ฮ˜ (๋น…์„ธํƒ€) โ€” ๋”ฑ ๋งž๋Š” ํฌ๊ธฐ
์œ„์•„๋ž˜๋กœ ๋™์‹œ์— ๋ฌถ์ผ ๋•Œ. ๋ณ‘ํ•ฉ ์ •๋ ฌ์˜ ์‹คํ–‰ ์‹œ๊ฐ„์€ ฮ˜(n log n)์ด์•ผ.
๋น„๊ต ์ •๋ ฌ์˜ ฮฉ(n log n) ํ•˜ํ•œ์€ ์–ด๋””์„œ ๋‚˜์˜ฌ๊นŒ? n๊ฐœ์˜ ์›์†Œ๋ฅผ ์ค„ ์„ธ์šฐ๋Š” ๋ฐฉ๋ฒ•์€ n!๊ฐ€์ง€์•ผ. ๋น„๊ต ํ•œ ๋ฒˆ์€ "์˜ˆ/์•„๋‹ˆ์˜ค" ๋‘ ๊ฐˆ๋ž˜๋กœ ๋‚˜๋‰˜๋‹ˆ๊นŒ, ๋น„๊ต k๋ฒˆ์œผ๋กœ ๊ตฌ๋ถ„ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์ตœ๋Œ€ 2แต๊ฐ€์ง€. ๋ชจ๋“  ์ˆœ์„œ๋ฅผ ๊ตฌ๋ถ„ํ•˜๋ ค๋ฉด 2แต โ‰ฅ n!์ด์–ด์•ผ ํ•˜๊ณ , ์Šคํ„ธ๋ง ๊ทผ์‚ฌ๋กœ logโ‚‚(n!) โ‰ˆ n logโ‚‚ n โˆ’ 1.44n์ด๋‹ˆ k๋Š” ๋Œ€๋žต n log n ์ด์ƒ์ด ๋ผ์•ผ ํ•ด. ์ด๋ ‡๊ฒŒ "์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ์ด๋ณด๋‹ค ๋น ๋ฅผ ์ˆ˜ ์—†๋‹ค"๋ฅผ ์ฆ๋ช…ํ•˜๋Š” ๊ฒŒ ๋ณต์žก๋„ ์ด๋ก ์˜ ์ง„์งœ ๋ฌ˜๋ฏธ์•ผ. ๊ทธ๋ฆฌ๊ณ  ๋ฐ”๋กœ ์ด๋Ÿฐ 'ํ•˜ํ•œ ์ฆ๋ช…'์ด P vs NP์—์„œ ์—„์ฒญ๋‚˜๊ฒŒ ์–ด๋ ต๋‹ค๋Š” ๊ฒŒ ์˜ค๋Š˜ ์ด์•ผ๊ธฐ์˜ ํ•ต์‹ฌ ๋ฐ˜์ „์ด๊ธฐ๋„ ํ•ด.

๐Ÿ“ˆ ๋‹คํ•ญ์‹ vs ์ง€์ˆ˜: ๋„˜์„ ์ˆ˜ ์—†๋Š” ๊ฐ•

์ด์ œ ์ง„์งœ ์ค‘์š”ํ•œ ๊ตฌ๋ถ„์ด ๋‚˜์™€. ์ฆ๊ฐ€ ์†๋„๋Š” ํฌ๊ฒŒ ๋‘ ๋ถ€๋ฅ˜๋กœ ๋‚˜๋‰˜์–ด.

๋ณต์žก๋„์ด๋ฆ„๋Œ€ํ‘œ ์˜ˆ์‹œn=10n=100
O(1)์ƒ์ˆ˜๋ฐฐ์—ด ์ธ๋ฑ์Šค ์ ‘๊ทผ11
O(log n)๋กœ๊ทธ์ด์ง„ ํƒ์ƒ‰์•ฝ 3.3์•ฝ 6.6
O(n)์„ ํ˜•์ตœ๋Œ“๊ฐ’ ์ฐพ๊ธฐ10100
O(n log n)์„ ํ˜• ๋กœ๊ทธ๋ณ‘ํ•ฉ ์ •๋ ฌ์•ฝ 33์•ฝ 664
O(nยฒ)์ œ๊ณฑ๋ฒ„๋ธ” ์ •๋ ฌ10010,000
O(nยณ)์„ธ์ œ๊ณฑ๋‹จ์ˆœ ํ–‰๋ ฌ ๊ณฑ์…ˆ1,0001,000,000
O(2โฟ)์ง€์ˆ˜๋ถ€๋ถ„์ง‘ํ•ฉ ์ „์ˆ˜ ์กฐ์‚ฌ1,024์•ฝ 1.27ร—10ยณโฐ
O(n!)ํŒฉํ† ๋ฆฌ์–ผ์ˆœ์—ด ์ „์ˆ˜ ์กฐ์‚ฌ3,628,800์•ฝ 9.33ร—10ยนโตโท

n=100์ผ ๋•Œ 2โฟ์ด ์•ฝ 1.27ร—10ยณโฐ์ด๋ผ๋Š” ๊ฒŒ ๊ฐ์ด ์™€? ์ดˆ๋‹น 10ยนโธ๋ฒˆ(์—‘์‚ฌํ”Œ๋กญ์Šค๊ธ‰) ์—ฐ์‚ฐํ•˜๋Š” ์Šˆํผ์ปดํ“จํ„ฐ๋กœ ๋Œ๋ ค๋„ ์•ฝ 1.27ร—10ยนยฒ์ดˆ, ๊ทธ๋Ÿฌ๋‹ˆ๊นŒ ๋Œ€๋žต 4๋งŒ ๋…„์ด ๊ฑธ๋ ค. n!์€ ๋งํ•  ๊ฒƒ๋„ ์—†๊ณ . ๋ฐ˜๋ฉด nยณ์€ n=100์ด๋ฉด 100๋งŒ ๋ฒˆ์ด๋ผ ์ผ๋ฐ˜ ๋…ธํŠธ๋ถ์œผ๋กœ ๋ˆˆ ๊นœ์งํ•  ์‚ฌ์ด์— ๋๋‚˜.

์ฆ๊ฐ€ ์†๋„ ๋ ˆ์ด์Šค 0 1000 2000 0 4 8 12 ์ž…๋ ฅ ํฌ๊ธฐ n nยฒ nยณ 2โฟ n! n=10 ๊ทผ์ฒ˜์—์„œ 2โฟ์ด nยณ์„ ์ถ”์›”

์‹ค์ œ ๊ฐ’์œผ๋กœ ๊ทธ๋ฆฐ ๊ณก์„ . ์ดˆ๋ฐ˜์—” nยณ์ด ๋” ์ปค ๋ณด์—ฌ๋„, n์ด 10์„ ๋„˜์œผ๋ฉด ์ง€์ˆ˜ ํ•จ์ˆ˜๊ฐ€ ์˜์˜ ์•ž์„œ ๋‚˜๊ฐ€.

๊ทธ๋ž˜ํ”„๋ฅผ ๋ณด๋ฉด ์žฌ๋ฐŒ๋Š” ํฌ์ธํŠธ๊ฐ€ ์žˆ์–ด. n์ด ์ž‘์„ ๋• nยณ์ด 2โฟ๋ณด๋‹ค ์˜คํžˆ๋ ค ํฌ๊ฑฐ๋“ . ๊ทธ๋ž˜์„œ ์ž‘์€ ๋ฐ์ดํ„ฐ๋งŒ ํ…Œ์ŠคํŠธํ•˜๋ฉด "์ง€์ˆ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ๊ดœ์ฐฎ๋„ค?" ํ•˜๊ณ  ์ฐฉ๊ฐํ•˜๊ธฐ ์‰ฌ์›Œ. ํ•˜์ง€๋งŒ n์ด ๋Œ€๋žต 10์„ ๋„˜์–ด์„œ๋Š” ์ˆœ๊ฐ„ 2โฟ์ด ์ถ”์›”ํ•˜๊ณ , ๊ทธ ๋‹ค์Œ๋ถ€ํ„ด ๊ฒฉ์ฐจ๊ฐ€ ์šฐ์ฃผ์ ์œผ๋กœ ๋ฒŒ์–ด์ ธ. ๋ณต์žก๋„ ๋ถ„์„์ด "ํฐ n์—์„œ์˜ ํ–‰๋™"์— ์ง‘์ฐฉํ•˜๋Š” ์ด์œ ๊ฐ€ ๋ฐ”๋กœ ์ด๊ฑฐ์•ผ.

๐Ÿ ์™œ ํ•˜ํ•„ '๋‹คํ•ญ ์‹œ๊ฐ„'์ด ํšจ์œจ์„ฑ์˜ ๊ธฐ์ค€์ผ๊นŒ

1965๋…„, ์žญ ์—๋“œ๋จผ์ฆˆ(Jack Edmonds)๋Š” ๋…ผ๋ฌธ ใ€ŒPaths, Trees, and Flowersใ€์—์„œ ๊ทธ๋ž˜ํ”„์˜ ์ตœ๋Œ€ ๋งค์นญ์„ ๋‹คํ•ญ ์‹œ๊ฐ„์— ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋‚ด๋†“์œผ๋ฉด์„œ, ๋‹คํ•ญ ์‹œ๊ฐ„์„ '์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜'์˜ ๊ธฐ์ค€์œผ๋กœ ์‚ผ์ž๊ณ  ์ œ์•ˆํ–ˆ์–ด. ๋น„์Šทํ•œ ์‹œ๊ธฐ์— ์•จ๋Ÿฐ ์ฝ”๋ฒ”(Alan Cobham)๋„ ๋‹คํ•ญ ์‹œ๊ฐ„ ๊ณ„์‚ฐ ๊ฐ€๋Šฅ์„ฑ์„ ๊ธฐ๊ณ„์™€ ๋ฌด๊ด€ํ•œ ๊ฐœ๋…์œผ๋กœ ์ •์‹ํ™”ํ–ˆ์ง€. ๊ทธ๋ž˜์„œ ์ด ์ƒ๊ฐ์„ ํ”ํžˆ ์ฝ”๋ฒ”โ€“์—๋“œ๋จผ์ฆˆ ๋…ผ์ œ๋ผ๊ณ  ๋ถˆ๋Ÿฌ.

๋‹คํ•ญ ์‹œ๊ฐ„์ด ๊ธฐ์ค€์œผ๋กœ ์‚ฌ๋ž‘๋ฐ›๋Š” ์ด์œ ๋Š” ์„ธ ๊ฐ€์ง€์•ผ.

ํ•ฉ์„ฑํ•ด๋„ ์•ˆ ๊นจ์ง„๋‹ค
๋‹คํ•ญ ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์•ˆ์—์„œ ๋‹คํ•ญ ์‹œ๊ฐ„ ์„œ๋ธŒ๋ฃจํ‹ด์„ ๋‹คํ•ญ ๋ฒˆ ํ˜ธ์ถœํ•ด๋„ ๊ฒฐ๊ณผ๋Š” ์—ฌ์ „ํžˆ ๋‹คํ•ญ ์‹œ๊ฐ„์ด์•ผ. ๋ ˆ๊ณ ์ฒ˜๋Ÿผ ์กฐ๋ฆฝ์ด ์ž์œ ๋กœ์›Œ.
๊ณ„์‚ฐ ๋ชจ๋ธ์ด ๋ฐ”๋€Œ์–ด๋„ ์‚ด์•„๋‚จ๋Š”๋‹ค
ํŠœ๋ง ๋จธ์‹ , ์‹ค์ œ ์ปดํ“จํ„ฐ์— ๊ฐ€๊นŒ์šด RAM ๋ชจ๋ธ ๋“ฑ ํ•ฉ๋ฆฌ์ ์ธ ๊ณ ์ „ ๊ณ„์‚ฐ ๋ชจ๋ธ๋ผ๋ฆฌ๋Š” ์„œ๋กœ๋ฅผ ๋‹คํ•ญ ์‹œ๊ฐ„ ์˜ค๋ฒ„ํ—ค๋“œ๋กœ ํ‰๋‚ด ๋‚ผ ์ˆ˜ ์žˆ์–ด. ๊ทธ๋ž˜์„œ "๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€๋ฆฐ๋‹ค"๋Š” ์„ฑ์งˆ์€ ๋ชจ๋ธ์— ๋”ฐ๋ผ ํ”๋“ค๋ฆฌ์ง€ ์•Š์•„.
์ง€์ˆ˜์™€์˜ ๊ฐ„๊ทน์ด ์••๋„์ ์ด๋‹ค
์ปดํ“จํ„ฐ๊ฐ€ 2๋ฐฐ ๋นจ๋ผ์ง€๋ฉด O(nยฒ) ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฐ™์€ ์‹œ๊ฐ„์— ์•ฝ 1.41๋ฐฐ ํฐ ์ž…๋ ฅ์„ ์ฒ˜๋ฆฌํ•˜์ง€๋งŒ, O(2โฟ) ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ณ ์ž‘ ์ž…๋ ฅ 1๊ฐœ๋ฅผ ๋” ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ์„ ๋ฟ์ด์•ผ.
์˜คํ•ด ์ฃผ์˜: "๋‹คํ•ญ ์‹œ๊ฐ„ = ์‹ค์ œ๋กœ ๋น ๋ฆ„"์€ ์•„๋‹ˆ์•ผ O(nยนโฐโฐ)๋„ ์—„์—ฐํžˆ ๋‹คํ•ญ ์‹œ๊ฐ„์ด์ง€๋งŒ ์‹ค์ œ๋กœ๋Š” ์“ธ ์ˆ˜ ์—†์–ด. ๋ฐ˜๋Œ€๋กœ ์ตœ์•…์˜ ๊ฒฝ์šฐ ์ง€์ˆ˜ ์‹œ๊ฐ„์ธ ๋‹จ์ฒด๋ฒ•(Simplex method)์€ ์‹ค๋ฌด์—์„œ ๋งค์šฐ ๋น ๋ฅด๊ฒŒ ์ž˜ ๋Œ์•„๊ฐ€. ๋‹คํ•ญ ์‹œ๊ฐ„์€ ์ด๋ก ์ ์œผ๋กœ ๊น”๋”ํ•œ ๊ฒฝ๊ณ„์„ ์ด์ง€, ์‹ค์šฉ์„ฑ์˜ ์™„๋ฒฝํ•œ ๋ณด์ฆ์„œ๋Š” ์•„๋‹ˆ๋ผ๋Š” ๊ฑธ ๊ธฐ์–ตํ•ด ๋‘ฌ. ๋‹ค๋งŒ ๊ฒฝํ—˜์ ์œผ๋กœ ์ž์—ฐ์Šค๋Ÿฌ์šด ๋ฌธ์ œ์—์„œ ๋‹คํ•ญ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ฐœ๊ฒฌ๋˜๋ฉด, ์ดํ›„ ์ง€์ˆ˜๊ฐ€ ์ž‘์€ ๊ฐœ์„ ํŒ์ด ๋‚˜์˜ค๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ๋‹ค๋Š” ์ ์ด ์ด ๊ธฐ์ค€์„ ๋ฒ„ํ‹ฐ๊ฒŒ ํ•ด์ฃผ๋Š” ํž˜์ด์•ผ.

๐Ÿค– 2. ๊ณ„์‚ฐ์„ ์ˆ˜ํ•™์œผ๋กœ: ํŠœ๋ง ๋จธ์‹ ๊ณผ ๊ฒฐ์ • ๋ฌธ์ œ

"๋ฌธ์ œ๊ฐ€ ์–ด๋ ต๋‹ค"๋ฅผ ์ˆ˜ํ•™์ ์œผ๋กœ ์ฆ๋ช…ํ•˜๋ ค๋ฉด ๋จผ์ € '๋ฌธ์ œ'์™€ '๊ณ„์‚ฐ'์„ ์ •ํ™•ํžˆ ์ •์˜ํ•ด์•ผ ํ•ด. ๋ง‰์—ฐํ•˜๊ฒŒ "์ด๊ฑฐ ์–ด๋ ต๋‹ค~"๋ผ๊ณ  ํ•˜๋ฉด ์ˆ˜ํ•™์ž๋“ค์ด ์•ˆ ๋ฐ›์•„์ฃผ๊ฑฐ๋“ .

โ“ ๊ฒฐ์ • ๋ฌธ์ œ: ์˜ˆ/์•„๋‹ˆ์˜ค๋กœ ๋‹ตํ•˜๋Š” ์งˆ๋ฌธ

๋ณต์žก๋„ ์ด๋ก ์€ ์ฃผ๋กœ ๊ฒฐ์ • ๋ฌธ์ œ(decision problem)๋ฅผ ๋‹ค๋ค„. ๋‹ต์ด "์˜ˆ" ์•„๋‹ˆ๋ฉด "์•„๋‹ˆ์˜ค"์ธ ์งˆ๋ฌธ์ด์•ผ. ์˜ˆ๋ฅผ ๋“ค๋ฉด:

โ€ข "์ด ๊ทธ๋ž˜ํ”„์—์„œ A์—์„œ B๊นŒ์ง€ ๊ธธ์ด 10 ์ดํ•˜์ธ ๊ฒฝ๋กœ๊ฐ€ ์žˆ๋Š”๊ฐ€?"
โ€ข "์ด ์ˆซ์ž๋Š” ์†Œ์ˆ˜์ธ๊ฐ€?"
โ€ข "์ด ์ด๋™ ๊ฑฐ๋ฆฌ๊ฐ€ 1,000km ์ดํ•˜์ธ ์™ธํŒ์› ์ˆœํšŒ ๊ฒฝ๋กœ๊ฐ€ ์žˆ๋Š”๊ฐ€?"

"์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋Š” ์–ผ๋งˆ์ธ๊ฐ€?" ๊ฐ™์€ ์ตœ์ ํ™” ๋ฌธ์ œ๋„, "๊ธธ์ด k ์ดํ•˜์ธ ๊ฒฝ๋กœ๊ฐ€ ์žˆ๋Š”๊ฐ€?"๋ผ๋Š” ๊ฒฐ์ • ๋ฌธ์ œ๋กœ ๋ฐ”๊ฟ€ ์ˆ˜ ์žˆ์–ด. ๊ทธ๋ฆฌ๊ณ  k๋ฅผ ์ด์ง„ ํƒ์ƒ‰ํ•˜๋ฉฐ ๊ฒฐ์ • ๋ฌธ์ œ๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ํ’€๋ฉด ์ตœ์ ๊ฐ’๋„ ์ฐพ์„ ์ˆ˜ ์žˆ์œผ๋‹ˆ, ๊ฒฐ์ • ๋ฌธ์ œ๋งŒ ์—ฐ๊ตฌํ•ด๋„ ๋ณธ์งˆ์„ ๋†“์น˜์ง€ ์•Š์•„. ํ˜•์‹์ ์œผ๋กœ๋Š” ๊ฒฐ์ • ๋ฌธ์ œ๋ฅผ "๋‹ต์ด '์˜ˆ'์ธ ์ž…๋ ฅ ๋ฌธ์ž์—ด๋“ค์˜ ์ง‘ํ•ฉ", ์ฆ‰ ์–ธ์–ด(language)๋กœ ๋ด.

โš™๏ธ ํŠœ๋ง ๋จธ์‹ : ๊ณ„์‚ฐ์˜ ํ‘œ์ค€ ๋ชจ๋ธ

1936๋…„ ์•จ๋Ÿฐ ํŠœ๋ง์ด ์ œ์•ˆํ•œ ํŠœ๋ง ๋จธ์‹ ์€ ๋ฌดํ•œํ•œ ํ…Œ์ดํ”„, ๊ทธ ์œ„๋ฅผ ์›€์ง์ด๋Š” ํ—ค๋“œ, ์œ ํ•œํ•œ ์ƒํƒœํ‘œ๋กœ ์ด๋ค„์ง„ ์•„์ฃผ ๋‹จ์ˆœํ•œ ๊ธฐ๊ณ„์•ผ. ๋‹จ์ˆœํ•ด ๋ณด์—ฌ๋„ ์˜ค๋Š˜๋‚  ์ปดํ“จํ„ฐ๊ฐ€ ํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ณ„์‚ฐ์„ (์‹œ๊ฐ„๋งŒ ์ถฉ๋ถ„ํ•˜๋‹ค๋ฉด) ํ•ด๋‚ผ ์ˆ˜ ์žˆ๋‹ค๊ณ  ์—ฌ๊ฒจ์ ธ. ์ด๊ฒŒ ์ฒ˜์น˜โ€“ํŠœ๋ง ๋…ผ์ œ์ง€.

์—ฌ๊ธฐ์„œ ๋‘ ์ข…๋ฅ˜์˜ ํŠœ๋ง ๋จธ์‹ ์ด ๋“ฑ์žฅํ•ด. ์ด ๊ตฌ๋ถ„์ด P์™€ NP๋ฅผ ๋‚˜๋ˆ„๋Š” ๊ฒฐ์ •์  ์—ด์‡ ์•ผ.

๐Ÿ”ต ๊ฒฐ์ •๋ก ์  ํŠœ๋ง ๋จธ์‹  (DTM)
๊ฐ ์ƒํ™ฉ์—์„œ ๋‹ค์Œ ๋™์ž‘์ด ๋”ฑ ํ•˜๋‚˜๋กœ ์ •ํ•ด์ ธ ์žˆ์–ด. ์šฐ๋ฆฌ๊ฐ€ ์“ฐ๋Š” ํ‰๋ฒ”ํ•œ ์ปดํ“จํ„ฐ๋ž‘ ๊ฐ™์€ ๋ฐฉ์‹์ด์•ผ. ํ•œ ๊ธธ๋งŒ ์„ฑ์‹คํžˆ ๊ฑธ์–ด๊ฐ€๋Š” ์‚ฐ์ฑ…์ž.
๐Ÿ”ด ๋น„๊ฒฐ์ •๋ก ์  ํŠœ๋ง ๋จธ์‹  (NTM)
ํ•œ ์ƒํ™ฉ์—์„œ ์—ฌ๋Ÿฌ ๊ฐˆ๋ž˜๋กœ ๋™์‹œ์— '๋ถ„๊ธฐ'ํ•  ์ˆ˜ ์žˆ์–ด. ๋ถ„๊ธฐ ์ค‘ ํ•˜๋‚˜๋ผ๋„ '์˜ˆ'์— ๋„๋‹ฌํ•˜๋ฉด ๋‹ต์€ '์˜ˆ'. ๊ฐˆ๋ฆผ๊ธธ๋งˆ๋‹ค ๋ถ„์‹ ์ˆ ์„ ์จ์„œ ๋ชจ๋“  ๊ธธ์„ ๋™์‹œ์— ๊ฐ€๋ณด๋Š” ๋‹Œ์ž ๊ฐ™์€ ์กด์žฌ.

๋น„๊ฒฐ์ •๋ก ์  ๊ธฐ๊ณ„๋Š” ์‹ค์ œ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ธฐ๊ณ„๊ฐ€ ์•„๋‹ˆ๋ผ ์‚ฌ๊ณ  ์‹คํ—˜์šฉ ์ˆ˜ํ•™์  ๋ชจ๋ธ์ด์•ผ. "์ •๋‹ต์„ ๊ธฐ๊ฐ€ ๋ง‰ํžˆ๊ฒŒ ์ฐ๋Š” ๋Šฅ๋ ฅ์ด ์žˆ๋‹ค๋ฉด?"์ด๋ผ๋Š” ๊ฐ€์ •์„ ํ˜•์‹ํ™”ํ•œ ๊ฑฐ์ง€.

โš–๏ธ 3. P์™€ NP, ๋“œ๋””์–ด ์ •์ฒด๋ฅผ ๋ฐํžˆ๋‹ค

๐ŸŸข ํด๋ž˜์Šค P: ๋น ๋ฅด๊ฒŒ 'ํ’€ ์ˆ˜' ์žˆ๋Š” ๋ฌธ์ œ๋“ค

P(Polynomial time)๋Š” ๊ฒฐ์ •๋ก ์  ํŠœ๋ง ๋จธ์‹ ์œผ๋กœ ๋‹คํ•ญ ์‹œ๊ฐ„ ์•ˆ์— ํ’€ ์ˆ˜ ์žˆ๋Š” ๊ฒฐ์ • ๋ฌธ์ œ๋“ค์˜ ๋ชจ์ž„์ด์•ผ. ์ •๋ ฌ, ์ตœ๋‹จ ๊ฒฝ๋กœ(๋‹ค์ต์ŠคํŠธ๋ผ), ์ตœ๋Œ€ ์œ ๋Ÿ‰, ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ ๊ณ„์‚ฐ ๋“ฑ์ด ์—ฌ๊ธฐ ์‚ด์•„.

P์— ๋“ค์–ด๊ฐ„ ์ค„ ๋ชฐ๋ž๋‹ค๊ฐ€ ๋‚˜์ค‘์— ํ™•์ธ๋œ ์œ ๋ช…ํ•œ ์‚ฌ๋ก€๋„ ์žˆ์–ด.

1979๋ ˆ์˜ค๋‹ˆ๋“œ ํ•˜์น˜์–€(Leonid Khachiyan)์ด ํƒ€์›์ฒด๋ฒ•์œผ๋กœ ์„ ํ˜•๊ณ„ํš๋ฒ•์ด ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€๋ฆฐ๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์˜€์–ด. ์ดํ›„ 1984๋…„ ์นด๋ฅด๋งˆ๋ฅด์นด๋ฅด(Narendra Karmarkar)์˜ ๋‚ด์ ๋ฒ•์ด ์‹ค์šฉ์ ์ธ ๋‹คํ•ญ ์‹œ๊ฐ„ ๋ฐฉ๋ฒ•์œผ๋กœ ํฐ ๋ฐ˜ํ–ฅ์„ ์ผ์œผ์ผฐ์ง€.
2002์ธ๋„ ๊ณต๊ณผ๋Œ€ํ•™ ์นธํ‘ธ๋ฅด์˜ ์•„๊ทธ๋ผ์™ˆ(Agrawal), ์นด์–„(Kayal), ์‚ญ์„ธ๋‚˜(Saxena)๊ฐ€ ์†Œ์ˆ˜ ํŒ์ •์„ ๊ฒฐ์ •๋ก ์  ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ•ด๊ฒฐํ•˜๋Š” AKS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐœํ‘œํ–ˆ์–ด(๋…ผ๋ฌธ ใ€ŒPRIMES is in Pใ€). ๋ฌด์ž‘์œ„์„ฑ ์—†์ด, ์–ด๋–ค ๊ฐ€์„ค์—๋„ ๊ธฐ๋Œ€์ง€ ์•Š๊ณ  ํ•ด๋‚ธ ๊ฒฐ๊ณผ๋ผ ํฐ ํ™”์ œ๊ฐ€ ๋์–ด.
2015๋ผ์Šฌ๋กœ ๋ฐ”๋ฐ”์ด(Lรกszlรณ Babai)๊ฐ€ ๊ทธ๋ž˜ํ”„ ๋™ํ˜• ๋ฌธ์ œ๋ฅผ ์ค€๋‹คํ•ญ ์‹œ๊ฐ„(quasi-polynomial time)์— ํ‘ธ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐœํ‘œํ–ˆ์–ด. ์•„์ง P์— ์†ํ•œ๋‹ค๋Š” ์ฆ๋ช…์€ ์•„๋‹ˆ์ง€๋งŒ, ์ง€์ˆ˜ ์‹œ๊ฐ„๋ณด๋‹ค ํ›จ์”ฌ ๋‹คํ•ญ ์‹œ๊ฐ„ ์ชฝ์— ๊ฐ€๊นŒ์›Œ์กŒ์ง€.
์†Œ์ˆ˜ ํŒ์ • โ‰  ์†Œ์ธ์ˆ˜๋ถ„ํ•ด "์ด ์ˆ˜๊ฐ€ ์†Œ์ˆ˜์ธ๊ฐ€?"๋Š” P์— ์†ํ•˜์ง€๋งŒ, "์ด ์ˆ˜๋ฅผ ์†Œ์ธ์ˆ˜๋กœ ๋ถ„ํ•ดํ•˜๋ผ"๋Š” ์ง€๊ธˆ๊นŒ์ง€ ๊ณ ์ „ ์ปดํ“จํ„ฐ์šฉ ๋‹คํ•ญ ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์•Œ๋ ค์ ธ ์žˆ์ง€ ์•Š์•„. ์ด ๋‘˜์€ ๋น„์Šทํ•ด ๋ณด์—ฌ๋„ ์™„์ „ํžˆ ๋‹ค๋ฅธ ๋ฌธ์ œ์•ผ. RSA ์•”ํ˜ธ์˜ ์•ˆ์ „์„ฑ์€ ํฐ ์ˆ˜์˜ ์†Œ์ธ์ˆ˜๋ถ„ํ•ด๊ฐ€ ํ˜„์‹ค์ ์œผ๋กœ ์–ด๋ ต๋‹ค๋Š” ๊ฐ€์ •์— ๊ธฐ๋Œ€๊ณ  ์žˆ์–ด.

๐Ÿ”ต ํด๋ž˜์Šค NP: ๋น ๋ฅด๊ฒŒ '๊ฒ€์ฆํ• ' ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋“ค

์ž, ์—ฌ๊ธฐ์„œ ๊ฐ€์žฅ ํ”ํ•œ ์˜คํ•ด๋ถ€ํ„ฐ ๋ฐ•์‚ด ๋‚ด๊ณ  ๊ฐ€์ž. NP๋Š” "Not Polynomial(๋‹คํ•ญ์ด ์•„๋‹˜)"์˜ ์•ฝ์ž๊ฐ€ ์•„๋‹ˆ์•ผ! Nondeterministic Polynomial time, ์ฆ‰ "๋น„๊ฒฐ์ •๋ก ์  ํŠœ๋ง ๋จธ์‹ ์œผ๋กœ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ"๋ผ๋Š” ๋œป์ด์•ผ.

๊ทธ๋Ÿฐ๋ฐ ์ด ์ •์˜๋Š” ์ด๋ ‡๊ฒŒ ๋ฐ”๊ฟ” ๋งํ•  ์ˆ˜ ์žˆ์–ด. ํ›จ์”ฌ ์ง๊ด€์ ์ด์•ผ.

NP = ๋‹ต์ด '์˜ˆ'์ผ ๋•Œ, ๊ทธ๊ฒƒ์„ ๋’ท๋ฐ›์นจํ•˜๋Š” ์งง์€ ์ฆ๊ฑฐ(์ธ์ฆ์„œ)๊ฐ€ ์กด์žฌํ•˜๊ณ ,
๊ทธ ์ฆ๊ฑฐ๊ฐ€ ๋งž๋Š”์ง€๋ฅผ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ™•์ธํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋“ค์˜ ๋ชจ์ž„

๋‘ ์ •์˜๊ฐ€ ๊ฐ™์€ ์ด์œ ๋„ ๊ฐ„๋‹จํ•ด. ๋น„๊ฒฐ์ •๋ก ์  ๊ธฐ๊ณ„๊ฐ€ '์ฐ์€' ๋ถ„๊ธฐ ๊ฒฝ๋กœ ์ž์ฒด๋ฅผ ์ฆ๊ฑฐ๋กœ ์‚ผ์œผ๋ฉด ๋˜๊ฑฐ๋“ . ๋ฐ˜๋Œ€๋กœ ์ฆ๊ฑฐ๊ฐ€ ์žˆ๋‹ค๋ฉด, ๋น„๊ฒฐ์ •๋ก ์  ๊ธฐ๊ณ„๋Š” ์ฆ๊ฑฐ๋ฅผ ํ•œ ๊ธ€์ž์”ฉ '์ฐ์–ด์„œ' ๋งŒ๋“  ๋‹ค์Œ ๊ฒ€์ฆํ•˜๋ฉด ๋˜๊ณ .

์Šค๋„์ฟ ๋กœ ์ƒ๊ฐํ•ด ๋ด. ๋นˆ 9ร—9 ์Šค๋„์ฟ ๋ฅผ ํ‘ธ๋Š” ๊ฑด ๋จธ๋ฆฌ๊ฐ€ ์•„ํ”„์ง€๋งŒ, ์นœ๊ตฌ๊ฐ€ ๋‹ค ์ฑ„์šด ํŒ์„ ๋ณด์—ฌ์ฃผ๋ฉด "๊ฐ€๋กœยท์„ธ๋กœยท๋ฐ•์Šค์— 1~9๊ฐ€ ํ•œ ๋ฒˆ์”ฉ ์žˆ๋‚˜?"๋งŒ ํ™•์ธํ•˜๋ฉด ๋ผ. ๊ธˆ๋ฐฉ ๋๋‚˜์ง€. (์ฐธ๊ณ ๋กœ ์ผ๋ฐ˜ํ™”ํ•œ nยฒร—nยฒ ์Šค๋„์ฟ ๋Š” NP-์™„์ „์ด๋ผ๋Š” ๊ฒƒ์ด ์ฆ๋ช…๋ผ ์žˆ์–ด.)

์ฐพ๊ธฐ๋Š” ์–ด๋ ต๊ณ , ํ™•์ธ์€ ์‰ฝ๋‹ค A B C D E F G 3์ƒ‰ ์น ํ•˜๊ธฐ: ์ด์›ƒํ•œ ์ ๋ผ๋ฆฌ ์ƒ‰์ด ๊ฐ™์œผ๋ฉด ์•ˆ ๋จ ์™„์„ฑ๋œ ์ƒ‰์น ์„ ๋ฐ›์œผ๋ฉด ์„  9๊ฐœ๋งŒ ๋ณด๋ฉด ๊ฒ€์ฆ ๋ ํ•˜์ง€๋งŒ ์ฒ˜์Œ๋ถ€ํ„ฐ ์ฐพ์œผ๋ ค๋ฉด ์ตœ๋Œ€ 3โท๊ฐ€์ง€๋ฅผ ๋”ฐ์ ธ์•ผ

๊ทธ๋ž˜ํ”„ 3์ƒ‰ ์น ํ•˜๊ธฐ๋Š” NP-์™„์ „ ๋ฌธ์ œ. ์ธ์ฆ์„œ(์ƒ‰์น  ๊ฒฐ๊ณผ)๋ฅผ ํ™•์ธํ•˜๋Š” ๋น„์šฉ์€ ๊ฐ„์„  ์ˆ˜์— ๋น„๋ก€ํ•ด.

์œ„ ๊ทธ๋ฆผ์—์„œ ์  7๊ฐœ๋ฅผ 3๊ฐ€์ง€ ์ƒ‰์œผ๋กœ ์น ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ 3โท = 2,187๊ฐ€์ง€์•ผ. ์ ์ด 70๊ฐœ๋ฉด 3โทโฐ โ‰ˆ 2.5ร—10ยณยณ๊ฐ€์ง€๊ฐ€ ๋˜์ง€. ํ•˜์ง€๋งŒ ๋ˆ„๊ฐ€ ์™„์„ฑ๋œ ์ƒ‰์น ์„ ๊ฑด๋„ค์ฃผ๋ฉด ์„  ํ•˜๋‚˜ํ•˜๋‚˜์˜ ์–‘ ๋ ์ƒ‰์ด ๋‹ค๋ฅธ์ง€๋งŒ ๋ณด๋ฉด ๋์ด์•ผ. ๊ฒ€์ฆ์€ ๊ฐ„์„  ์ˆ˜๋งŒํผ, ํƒ์ƒ‰์€ ์ง€์ˆ˜๋งŒํผ. ์ด ๋น„๋Œ€์นญ์ด NP์˜ ์ •์ฒด์•ผ.

๐Ÿค” ๊ทธ๋ž˜์„œ P vs NP ๋ฌธ์ œ๋ž€?

P์— ์†ํ•œ ๋ฌธ์ œ๋Š” ๋ชจ๋‘ NP์—๋„ ์†ํ•ด. ์ง์ ‘ ํ’€ ์ˆ˜ ์žˆ์œผ๋ฉด, ์ฆ๊ฑฐ ์—†์ด๋„ ์ง์ ‘ ํ’€์–ด์„œ ํ™•์ธํ•˜๋ฉด ๋˜๋‹ˆ๊นŒ. ์ฆ‰ P โІ NP๋Š” ํ™•์‹คํ•ด. ๋ฌธ์ œ๋Š” ๊ทธ ๋ฐ˜๋Œ€์•ผ.

P vs NP ๋ฌธ์ œ์˜ ํ•ต์‹ฌ ์งˆ๋ฌธ P = NP ์ธ๊ฐ€? ์ฆ‰ "๋‹ต์„ ๋น ๋ฅด๊ฒŒ ๊ฒ€์ฆํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋ฌธ์ œ๋Š”, ๋‹ต์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์„ ์ˆ˜๋„ ์žˆ๋Š”๊ฐ€?"
๋Œ€๋ถ€๋ถ„์˜ ์—ฐ๊ตฌ์ž๋Š” P โ‰  NP๋ผ๊ณ  ๋ฏฟ์ง€๋งŒ, 2000๋…„ ํด๋ ˆ์ด ์ˆ˜ํ•™์—ฐ๊ตฌ์†Œ๊ฐ€ ๋ฐ€๋ ˆ๋‹ˆ์—„ ๋ฌธ์ œ๋กœ ์ง€์ •ํ•˜๊ณ  ์ƒ๊ธˆ 100๋งŒ ๋‹ฌ๋Ÿฌ๋ฅผ ๊ฑด ์ดํ›„ ์ง€๊ธˆ๊นŒ์ง€๋„ ์ฆ๋ช…๋œ ์ ์ด ์—†์–ด.

์žฌ๋ฐŒ๋Š” ์—ญ์‚ฌ ํ•œ ํ† ๋ง‰. 1956๋…„ ์ฟ ๋ฅดํŠธ ๊ดด๋ธ์€ ์กด ํฐ ๋…ธ์ด๋งŒ์—๊ฒŒ ๋ณด๋‚ธ ํŽธ์ง€์—์„œ, ์ˆ˜ํ•™ ์ •๋ฆฌ์˜ ๊ธธ์ด n ์ดํ•˜ ์ฆ๋ช…์„ ์ฐพ๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ๋‹จ๊ณ„ ์ˆ˜๊ฐ€ n์— ๋Œ€ํ•ด ์„ ํ˜•์ด๋‚˜ ์ œ๊ณฑ ์ •๋„๋กœ๋งŒ ๋Š˜์–ด๋‚  ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ๋ฌผ์—ˆ์–ด. ์ด๊ฒŒ ์‚ฌ์‹ค์ƒ P vs NP์˜ ์›ํ˜•์ด๋ผ๋Š” ํ‰๊ฐ€๋ฅผ ๋ฐ›์•„. ์ด ํŽธ์ง€๋Š” 1980๋…„๋Œ€ ํ›„๋ฐ˜์—์•ผ ๊ณต๊ฐœ๋˜์–ด ํ•™๊ณ„๋ฅผ ๋†€๋ผ๊ฒŒ ํ–ˆ์ง€. ํฐ ๋…ธ์ด๋งŒ์€ ๋‹น์‹œ ํˆฌ๋ณ‘ ์ค‘์ด๋ผ ๋‹ต์žฅ์„ ํ•˜์ง€ ๋ชปํ–ˆ๋‹ค๊ณ  ์•Œ๋ ค์ ธ ์žˆ์–ด.

๐Ÿ”— 4. ํ™˜์›: ๋ฌธ์ œ๋ผ๋ฆฌ ์ค„ ์„ธ์šฐ๊ธฐ

"์ด ๋ฌธ์ œ๊ฐ€ ์ € ๋ฌธ์ œ๋ณด๋‹ค ์–ด๋ ต์ง€ ์•Š๋‹ค"๋ฅผ ์–ด๋–ป๊ฒŒ ์ฆ๋ช…ํ• ๊นŒ? ์—ฌ๊ธฐ์„œ ๋ณต์žก๋„ ์ด๋ก ์˜ ํ•„์‚ด๊ธฐ, ํ™˜์›(reduction)์ด ๋“ฑ์žฅํ•ด.

๐Ÿ”„ ๋‹คํ•ญ ์‹œ๊ฐ„ ํ™˜์›์ด๋ž€

๋ฌธ์ œ A๋ฅผ ๋ฌธ์ œ B๋กœ ๋‹คํ•ญ ์‹œ๊ฐ„ ํ™˜์›ํ•œ๋‹ค๋Š” ๊ฑด, A์˜ ์ž…๋ ฅ x๋ฅผ B์˜ ์ž…๋ ฅ f(x)๋กœ ๋ฐ”๊พธ๋Š” ๋‹คํ•ญ ์‹œ๊ฐ„ ๋ณ€ํ™˜ f๊ฐ€ ์žˆ์–ด์„œ "x๊ฐ€ A์—์„œ ์˜ˆ โ‡” f(x)๊ฐ€ B์—์„œ ์˜ˆ"๊ฐ€ ์„ฑ๋ฆฝํ•œ๋‹ค๋Š” ๋œป์ด์•ผ. ๊ธฐํ˜ธ๋กœ A โ‰คโ‚š B๋ผ๊ณ  ์จ.

๋น„์œ ํ•˜์ž๋ฉด ์ด๋ž˜. ๋„ˆ๋Š” ์˜์–ด๋ฅผ ๋ชป ํ•˜์ง€๋งŒ ๋ฒˆ์—ญ๊ธฐ๋Š” ๋น ๋ฅด๊ฒŒ ๋Œ๋ฆด ์ˆ˜ ์žˆ์–ด. ์˜์–ด ํ€ด์ฆˆ(A)๋ฅผ ํ•œ๊ตญ์–ด ํ€ด์ฆˆ(B)๋กœ ๋ฒˆ์—ญํ•ด์„œ ํ’€๋ฉด, A๋Š” B๋ณด๋‹ค ์–ด๋ ต์ง€ ์•Š๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์ง€. ๊ทธ๋ž˜์„œ A โ‰คโ‚š B์ด๊ณ  B๊ฐ€ P์— ์†ํ•œ๋‹ค๋ฉด A๋„ P์— ์†ํ•ด.

์ด ๋…ผ๋ฆฌ๋ฅผ ๊ฑฐ๊พธ๋กœ ์“ฐ๋ฉด ๋” ๊ฐ•๋ ฅํ•ด์ ธ. A๊ฐ€ ์–ด๋ ต๋‹ค๊ณ  ์•Œ๋ ค์ ธ ์žˆ๋Š”๋ฐ A โ‰คโ‚š B๋ผ๋ฉด, B๋„ ์ตœ์†Œํ•œ ๊ทธ๋งŒํผ ์–ด๋ ต๋‹ค. ์ƒˆ๋กœ์šด ๋ฌธ์ œ์˜ ์–ด๋ ค์›€์„ ์ฆ๋ช…ํ•  ๋•Œ ์ด ๋ฐฉํ–ฅ์„ ์ฃผ๋กœ ์จ.

๐Ÿ‘‘ NP-๋‚œํ•ด์™€ NP-์™„์ „

NP-๋‚œํ•ด (NP-hard)
NP์˜ ๋ชจ๋“  ๋ฌธ์ œ๋ฅผ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ™˜์›๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ. NP ์•ˆ์— ์žˆ์„ ํ•„์š”๋Š” ์—†์–ด. ์ •์ง€ ๋ฌธ์ œ์ฒ˜๋Ÿผ ์•„์˜ˆ ๊ฒฐ์ • ๋ถˆ๊ฐ€๋Šฅํ•œ ๋ฌธ์ œ๋„ NP-๋‚œํ•ด์•ผ.
NP-์™„์ „ (NP-complete)
NP-๋‚œํ•ด์ด๋ฉด์„œ ๋™์‹œ์— NP์— ์†ํ•˜๋Š” ๋ฌธ์ œ. NP ์•ˆ์˜ '์ตœ์ข… ๋ณด์Šค'๋“ค์ด์•ผ.

NP-์™„์ „ ๋ฌธ์ œ๊ฐ€ ์™œ ๊ทธ๋ ‡๊ฒŒ ์ค‘์š”ํ•˜๋ƒ๋ฉด, NP-์™„์ „ ๋ฌธ์ œ ๋‹จ ํ•˜๋‚˜๋ผ๋„ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€๋ฆฌ๋ฉด NP ์ „์ฒด๊ฐ€ P๋กœ ๋ฌด๋„ˆ์ง€๊ธฐ ๋•Œ๋ฌธ์ด์•ผ. ๋ชจ๋“  NP ๋ฌธ์ œ๊ฐ€ ๊ทธ ๋ฌธ์ œ๋กœ ํ™˜์›๋˜๋‹ˆ๊นŒ. ๋ฐ˜๋Œ€๋กœ NP-์™„์ „ ๋ฌธ์ œ ํ•˜๋‚˜๋ผ๋„ ๋‹คํ•ญ ์‹œ๊ฐ„์— ์•ˆ ํ’€๋ฆฐ๋‹ค๋Š” ๊ฒŒ ์ฆ๋ช…๋˜๋ฉด P โ‰  NP๊ฐ€ ํ™•์ •๋˜๊ณ , NP-์™„์ „ ๋ฌธ์ œ๋Š” ์ „๋ถ€ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€ ์ˆ˜ ์—†๊ฒŒ ๋˜์ง€. ์ˆ˜์ฒœ ๊ฐœ์˜ ๋ฌธ์ œ๊ฐ€ ํ•œ ๋ฐฐ๋ฅผ ํƒ„ ์šด๋ช… ๊ณต๋™์ฒด์ธ ์…ˆ์ด์•ผ.

๐Ÿงจ ์ฟกโ€“๋ ˆ๋นˆ ์ •๋ฆฌ: ์ฒซ ๋ฒˆ์งธ NP-์™„์ „ ๋ฌธ์ œ

๊ทธ๋Ÿฐ๋ฐ "๋ชจ๋“  NP ๋ฌธ์ œ๊ฐ€ ํ™˜์›๋œ๋‹ค"๋ฅผ ์ฒ˜์Œ์— ์–ด๋–ป๊ฒŒ ์ฆ๋ช…ํ–ˆ์„๊นŒ? NP ๋ฌธ์ œ๋Š” ๋ฌดํ•œํžˆ ๋งŽ์€๋ฐ ๋ง์ด์•ผ. ์ด ๋ฒฝ์„ ์ฒ˜์Œ ๋„˜์€ ๊ฒŒ ์ฟกโ€“๋ ˆ๋นˆ ์ •๋ฆฌ์•ผ.

1971์Šคํ‹ฐ๋ธ ์ฟก(Stephen Cook)์ด ๋…ผ๋ฌธ ใ€ŒThe Complexity of Theorem-Proving Proceduresใ€์—์„œ SAT(๋ถˆ ๋งŒ์กฑ ๊ฐ€๋Šฅ์„ฑ ๋ฌธ์ œ)๊ฐ€ NP-์™„์ „์ž„์„ ์ฆ๋ช…ํ–ˆ์–ด. ์ฟก์€ ์ด ์—…์  ๋“ฑ์œผ๋กœ 1982๋…„ ํŠœ๋ง์ƒ์„ ๋ฐ›์•˜์–ด.
1973์†Œ๋ จ์˜ ๋ ˆ์˜ค๋‹ˆ๋“œ ๋ ˆ๋นˆ(Leonid Levin)์ด ๋…๋ฆฝ์ ์œผ๋กœ ๋น„์Šทํ•œ ๊ฒฐ๊ณผ(๋ณดํŽธ ํƒ์ƒ‰ ๋ฌธ์ œ)๋ฅผ ๋ฐœํ‘œํ–ˆ์–ด. ๊ทธ๋ž˜์„œ ๋‘˜์˜ ์ด๋ฆ„์„ ํ•จ๊ป˜ ๋ถ™์—ฌ ๋ถˆ๋Ÿฌ.
1972๋ฆฌ์ฒ˜๋“œ ์นดํ”„(Richard Karp)๊ฐ€ ๋…ผ๋ฌธ ใ€ŒReducibility Among Combinatorial Problemsใ€์—์„œ 21๊ฐœ์˜ ์กฐํ•ฉ ๋ฌธ์ œ๊ฐ€ NP-์™„์ „์ž„์„ ๋ณด์˜€์–ด. ํด๋ฆฌํฌ, ์ •์  ๋ฎ๊ฐœ, ํ•ด๋ฐ€ํ„ด ์ˆœํ™˜, ๊ทธ๋ž˜ํ”„ ์ƒ‰์น , ๋ฐฐ๋‚ญ ๋ฌธ์ œ ๋“ฑ์ด ์ด๋•Œ ์ค„์ค„์ด ํ•ฉ๋ฅ˜ํ–ˆ์ง€. ์นดํ”„๋Š” 1985๋…„ ํŠœ๋ง์ƒ์„ ๋ฐ›์•˜์–ด.
1979๋งˆ์ดํด ๊ฐœ๋ฆฌ(Michael Garey)์™€ ๋ฐ์ด๋น„๋“œ ์กด์Šจ(David Johnson)์˜ ์ฑ… ใ€ŽComputers and Intractabilityใ€๊ฐ€ 300๊ฐœ ์ด์ƒ์˜ NP-์™„์ „ ๋ฌธ์ œ๋ฅผ ์ •๋ฆฌํ•˜๋ฉฐ ์ด ๋ถ„์•ผ์˜ ๊ต๊ณผ์„œ๊ฐ€ ๋์–ด.

์ฟกโ€“๋ ˆ๋นˆ ์ •๋ฆฌ์˜ ์ฆ๋ช… ์•„์ด๋””์–ด๋ฅผ ๊ฐ„๋‹จํžˆ ๋ง›๋ณด์ž. NP์˜ ์•„๋ฌด ๋ฌธ์ œ๋‚˜ ํ•˜๋‚˜ ๊ณ ๋ฅด๋ฉด, ๊ทธ ๋ฌธ์ œ๋ฅผ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€์–ด๋‚ด๋Š” ๋น„๊ฒฐ์ •๋ก ์  ํŠœ๋ง ๋จธ์‹  M์ด ์žˆ์–ด. M์ด ์ž…๋ ฅ x์—์„œ p(n) ๋‹จ๊ณ„ ๋™์•ˆ ์›€์ง์ด๋Š” ๋ชจ์Šต์„ p(n)ร—p(n) ํฌ๊ธฐ์˜ ํ‘œ(๊ณ„์‚ฐ ๊ธฐ๋ก, tableau)๋กœ ๊ทธ๋ฆด ์ˆ˜ ์žˆ์ง€. ๊ฐ ์นธ์—๋Š” "์‹œ๊ฐ t์— ํ…Œ์ดํ”„ ์นธ i์— ๋ฌด์Šจ ๊ธฐํ˜ธ๊ฐ€ ์žˆ๋Š”๊ฐ€, ํ—ค๋“œ๋Š” ์–ด๋””์— ์žˆ๊ณ  ์ƒํƒœ๋Š” ๋ฌด์—‡์ธ๊ฐ€"๊ฐ€ ๋“ค์–ด๊ฐ€.

ํ‘œ์˜ ๊ฐ ์นธยท๊ฐ ๊ธฐํ˜ธ๋งˆ๋‹ค "์ฐธ/๊ฑฐ์ง“" ๋ณ€์ˆ˜๋ฅผ ํ•˜๋‚˜์”ฉ ๋งŒ๋“ ๋‹ค.
"๊ฐ ์นธ์—๋Š” ์ •ํ™•ํžˆ ํ•˜๋‚˜์˜ ๊ธฐํ˜ธ๋งŒ ์žˆ๋‹ค"๋ฅผ ๋ถˆ ๋…ผ๋ฆฌ์‹์œผ๋กœ ์“ด๋‹ค.
"์ฒซ ์ค„์€ ์ž…๋ ฅ x๋กœ ์‹œ์ž‘ํ•˜๋Š” ์ดˆ๊ธฐ ์ƒํƒœ๋‹ค"๋ฅผ ๋…ผ๋ฆฌ์‹์œผ๋กœ ์“ด๋‹ค.
"์œ—์ค„์—์„œ ์•„๋žซ์ค„๋กœ๋Š” M์˜ ์ „์ด ๊ทœ์น™๋Œ€๋กœ๋งŒ ๋ฐ”๋€๋‹ค"๋ฅผ ๊ตญ์†Œ์ ์ธ ์ž‘์€ ์ฐฝ(2ร—3 ์นธ ์ •๋„) ๋‹จ์œ„์˜ ๋…ผ๋ฆฌ์‹์œผ๋กœ ์“ด๋‹ค.
"์–ด๋А ์‹œ์ ์—”๊ฐ€ ์ˆ˜๋ฝ ์ƒํƒœ์— ๋„๋‹ฌํ•œ๋‹ค"๋ฅผ ๋…ผ๋ฆฌ์‹์œผ๋กœ ์“ด๋‹ค. ์ด ์ „๋ถ€๋ฅผ AND๋กœ ๋ฌถ์œผ๋ฉด, ์ด ๊ฑฐ๋Œ€ํ•œ ์‹์ด ๋งŒ์กฑ ๊ฐ€๋Šฅํ•  ๋•Œ์—๋งŒ M์ด x๋ฅผ ์ˆ˜๋ฝํ•œ๋‹ค.

์‹์˜ ํฌ๊ธฐ๋Š” ํ‘œ ํฌ๊ธฐ์— ๋น„๋ก€ํ•˜๋‹ˆ ๋‹คํ•ญ์‹ ํฌ๊ธฐ์ด๊ณ , ๋งŒ๋“œ๋Š” ๋ฐ๋„ ๋‹คํ•ญ ์‹œ๊ฐ„์ด๋ฉด ์ถฉ๋ถ„ํ•ด. ๊ฒฐ๊ตญ "๋ชจ๋“  NP ๊ณ„์‚ฐ์€ ๋…ผ๋ฆฌ์‹ ํ•˜๋‚˜๋กœ ๋ฒˆ์—ญ๋œ๋‹ค"๋Š” ๊ฒŒ ํ•ต์‹ฌ์ด์•ผ. ๊ณ„์‚ฐ์ด๋ผ๋Š” ๋™์ ์ธ ๊ณผ์ •์„ ์ •์ ์ธ ๋…ผ๋ฆฌ ํผ์ฆ๋กœ ์–ผ๋ ค๋ฒ„๋ฆฐ ์…ˆ์ด์ง€. ์ฒ˜์Œ ๋ฐฐ์šธ ๋•Œ ์†Œ๋ฆ„ ๋‹๋Š” ํฌ์ธํŠธ์•ผ.

โ›“๏ธ ํ™˜์›์˜ ์‚ฌ์Šฌ

SAT๊ฐ€ ์ฒซ ๋‹จ์ถ”๋ฅผ ๋ผ์šด ๋’ค๋กœ๋Š” ์ผ์ด ์‰ฌ์›Œ์กŒ์–ด. ์ƒˆ ๋ฌธ์ œ B๊ฐ€ NP-์™„์ „์ž„์„ ๋ณด์ด๋ ค๋ฉด ๋‘ ๊ฐ€์ง€๋งŒ ํ•˜๋ฉด ๋˜๊ฑฐ๋“ .

NP-์™„์ „ ์ฆ๋ช… ๋ ˆ์‹œํ”ผ โ‘  B๊ฐ€ NP์— ์†ํ•จ์„ ๋ณด์ธ๋‹ค (์งง์€ ์ฆ๊ฑฐ + ๋‹คํ•ญ ์‹œ๊ฐ„ ๊ฒ€์ฆ๊ธฐ).
โ‘ก ์ด๋ฏธ NP-์™„์ „์œผ๋กœ ์•Œ๋ ค์ง„ ๋ฌธ์ œ A๋ฅผ ๊ณจ๋ผ A โ‰คโ‚š B์ž„์„ ๋ณด์ธ๋‹ค.
ํ™˜์› ๊ด€๊ณ„๋Š” ์ถ”์ด์ ์ด๋ผ, NP์˜ ๋ชจ๋“  ๋ฌธ์ œ โ†’ A โ†’ B๋กœ ์—ฐ๊ฒฐ๋ผ B๋„ NP-์™„์ „์ด ๋ผ.

์˜ˆ๋ฅผ ๋“ค์–ด ๋Œ€ํ‘œ์ ์ธ ์—ฐ์‡„๋Š” SAT โ†’ 3-SAT โ†’ ๋…๋ฆฝ ์ง‘ํ•ฉ โ†’ ํด๋ฆฌํฌ / ์ •์  ๋ฎ๊ฐœ, ๊ทธ๋ฆฌ๊ณ  3-SAT โ†’ 3์ƒ‰ ์น ํ•˜๊ธฐ, 3-SAT โ†’ ํ•ด๋ฐ€ํ„ด ์ˆœํ™˜ โ†’ ์™ธํŒ์› ๋ฌธ์ œ(๊ฒฐ์ • ๋ฒ„์ „) ๊ฐ™์€ ์‹์ด์•ผ. ์ˆ˜์ฒœ ๊ฐœ์˜ ๋ฌธ์ œ๊ฐ€ ์ด๋ ‡๊ฒŒ ๊ฑฐ๋Œ€ํ•œ ๊ฑฐ๋ฏธ์ค„์ฒ˜๋Ÿผ ์ด์–ด์ ธ ์žˆ์–ด.

๐Ÿ” ๋ง›๋ณด๊ธฐ: 3-SAT์—์„œ ๋…๋ฆฝ ์ง‘ํ•ฉ์œผ๋กœ

ํ™˜์›์ด ์‹ค์ œ๋กœ ์–ด๋–ป๊ฒŒ ์ƒ๊ฒผ๋Š”์ง€ ํ•˜๋‚˜๋งŒ ์†์œผ๋กœ ๋งŒ์ ธ๋ณด์ž.

3-SAT: ๊ฐ ์ ˆ(clause)์— ๋ฆฌํ„ฐ๋Ÿด์ด 3๊ฐœ์”ฉ ์žˆ๋Š” ๋…ผ๋ฆฌ์‹, ์˜ˆ๋ฅผ ๋“ค์–ด (xโ‚ โˆจ ยฌxโ‚‚ โˆจ xโ‚ƒ) โˆง (ยฌxโ‚ โˆจ xโ‚‚ โˆจ xโ‚ƒ)์ด ์ฐธ์ด ๋˜๋„๋ก ๋ณ€์ˆ˜ ๊ฐ’์„ ์ •ํ•  ์ˆ˜ ์žˆ๋Š”๊ฐ€?
๋…๋ฆฝ ์ง‘ํ•ฉ: ๊ทธ๋ž˜ํ”„์—์„œ ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์€ ๊ผญ์ง“์  k๊ฐœ๋ฅผ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š”๊ฐ€?

๋ณ€ํ™˜ ๋ฐฉ๋ฒ•์€ ์ด๋ž˜.
โ€ข ์ ˆ ํ•˜๋‚˜๋‹น ๊ผญ์ง“์  3๊ฐœ์งœ๋ฆฌ ์‚ผ๊ฐํ˜•์„ ๋งŒ๋“ ๋‹ค (๊ฐ ๊ผญ์ง“์  = ๊ทธ ์ ˆ์˜ ๋ฆฌํ„ฐ๋Ÿด).
โ€ข ์„œ๋กœ ๋ชจ์ˆœ์ธ ๋ฆฌํ„ฐ๋Ÿด(xแตข์™€ ยฌxแตข)๋ผ๋ฆฌ ์„ ์„ ์ž‡๋Š”๋‹ค.
โ€ข k = ์ ˆ์˜ ๊ฐœ์ˆ˜๋กœ ๋‘”๋‹ค.

์‚ผ๊ฐํ˜• ์•ˆ์—์„œ๋Š” ๊ผญ์ง“์ ์„ ์ตœ๋Œ€ ํ•˜๋‚˜๋งŒ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ์œผ๋‹ˆ, ํฌ๊ธฐ k์ธ ๋…๋ฆฝ ์ง‘ํ•ฉ์€ "์ ˆ๋งˆ๋‹ค ์ฐธ์ด ๋  ๋ฆฌํ„ฐ๋Ÿด์„ ํ•˜๋‚˜์”ฉ ๊ณ ๋ฅด๋Š” ๊ฒƒ"๊ณผ ๊ฐ™์•„. ๋ชจ์ˆœ๋˜๋Š” ๋ฆฌํ„ฐ๋Ÿด ์‚ฌ์ด์—” ์„ ์ด ์žˆ์œผ๋‹ˆ ๋™์‹œ์— ๊ณ ๋ฅผ ์ˆ˜ ์—†๊ณ . ๊ทธ๋ž˜์„œ ์‹์ด ๋งŒ์กฑ ๊ฐ€๋Šฅ โ‡” ํฌ๊ธฐ k ๋…๋ฆฝ ์ง‘ํ•ฉ ์กด์žฌ๊ฐ€ ์ •ํ™•ํžˆ ์„ฑ๋ฆฝํ•ด. ๋ณ€ํ™˜์€ ์ ˆ ๊ฐœ์ˆ˜์— ๋Œ€ํ•ด ๋‹คํ•ญ ์‹œ๊ฐ„์ด๋ฉด ์ถฉ๋ถ„ํ•˜๊ณ . ๊น”๋”ํ•˜์ง€?

๐Ÿ—บ๏ธ 5. NP-์™„์ „ ๋ฌธ์ œ ๋„๊ฐ

NP-์™„์ „ ๋ฌธ์ œ๋“ค์€ ์ƒ๊ฐ๋ณด๋‹ค ์šฐ๋ฆฌ ์ƒํ™œ ๊ฐ€๊นŒ์ด์— ์žˆ์–ด. ํƒ๋ฐฐ ๊ฒฝ๋กœ, ์‹œ๊ฐ„ํ‘œ ์งœ๊ธฐ, ๋ฐ˜๋„์ฒด ๋ฐฐ์น˜, ๋‹จ๋ฐฑ์งˆ ๊ตฌ์กฐ ๋“ฑ ๊ณณ๊ณณ์— ์ˆจ์–ด ์žˆ์ง€.

๋ฌธ์ œ์งˆ๋ฌธ (๊ฒฐ์ • ๋ฒ„์ „)ํ˜„์‹ค ์† ๋ชจ์Šต
SAT / 3-SAT๋…ผ๋ฆฌ์‹์„ ์ฐธ์œผ๋กœ ๋งŒ๋“œ๋Š” ๋ณ€์ˆ˜ ๋ฐฐ์ •์ด ์žˆ๋Š”๊ฐ€?ํ•˜๋“œ์›จ์–ดยท์†Œํ”„ํŠธ์›จ์–ด ๊ฒ€์ฆ, ์ œ์•ฝ ์ถฉ์กฑ
์™ธํŒ์› ๋ฌธ์ œ(TSP)๋ชจ๋“  ๋„์‹œ๋ฅผ ํ•œ ๋ฒˆ์”ฉ ๋Œ๊ณ  ์˜ค๋Š” ์ด ๊ฑฐ๋ฆฌ k ์ดํ•˜ ๊ฒฝ๋กœ๊ฐ€ ์žˆ๋Š”๊ฐ€?๋ฌผ๋ฅ˜ ๋ฐฐ์†ก, ๋“œ๋ฆด ์ฒœ๊ณต ์ˆœ์„œ
๋ฐฐ๋‚ญ ๋ฌธ์ œ๋ฌด๊ฒŒ W ์ดํ•˜๋กœ ๊ฐ€์น˜ V ์ด์ƒ์„ ๋‹ด์„ ์ˆ˜ ์žˆ๋Š”๊ฐ€?์˜ˆ์‚ฐ ๋ฐฐ๋ถ„, ์ž์› ํ• ๋‹น
๊ทธ๋ž˜ํ”„ ์ƒ‰์น (kโ‰ฅ3)์ธ์ ‘ํ•œ ๊ผญ์ง“์ ์ด ๋‹ค๋ฅธ ์ƒ‰์ด ๋˜๊ฒŒ k์ƒ‰์œผ๋กœ ์น ํ•  ์ˆ˜ ์žˆ๋Š”๊ฐ€?์‹œํ—˜ ์‹œ๊ฐ„ํ‘œ, ๋ ˆ์ง€์Šคํ„ฐ ํ• ๋‹น, ์ฃผํŒŒ์ˆ˜ ๋ฐฐ์ •
ํด๋ฆฌํฌ์„œ๋กœ ๋ชจ๋‘ ์—ฐ๊ฒฐ๋œ ๊ผญ์ง“์  k๊ฐœ๊ฐ€ ์žˆ๋Š”๊ฐ€?์†Œ์…œ ๋„คํŠธ์›Œํฌ ๊ตฐ์ง‘ ๋ถ„์„
ํ•ด๋ฐ€ํ„ด ์ˆœํ™˜๋ชจ๋“  ๊ผญ์ง“์ ์„ ์ •ํ™•ํžˆ ํ•œ ๋ฒˆ์”ฉ ์ง€๋‚˜๋Š” ์ˆœํ™˜์ด ์žˆ๋Š”๊ฐ€?ํšŒ๋กœ ์„ค๊ณ„, ๊ฒฝ๋กœ ๊ณ„ํš
๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉํ•ฉ์ด ์ •ํ™•ํžˆ T๊ฐ€ ๋˜๋Š” ๋ถ€๋ถ„์ง‘ํ•ฉ์ด ์žˆ๋Š”๊ฐ€?ํšŒ๊ณ„ ๋Œ€์‚ฌ, ์•”ํ˜ธ ์—ฐ๊ตฌ

๐Ÿ˜ฎ ํ•œ ๋— ์ฐจ์ด๋กœ ์šด๋ช…์ด ๊ฐˆ๋ฆฌ๋Š” ๋ฌธ์ œ ์Œ

๋ณต์žก๋„ ์ด๋ก ์—์„œ ๊ฐ€์žฅ ์‹ ๊ธฐํ•œ ์žฅ๋ฉด ์ค‘ ํ•˜๋‚˜๋Š”, ๊ฑฐ์˜ ๋˜‘๊ฐ™์•„ ๋ณด์ด๋Š” ๋ฌธ์ œ๊ฐ€ P์™€ NP-์™„์ „์œผ๋กœ ๊ฐˆ๋ผ์ง€๋Š” ์ˆœ๊ฐ„์ด์•ผ.

๐ŸŸข P์— ์†ํ•จ
โ€ข 2-SAT (์ ˆ๋งˆ๋‹ค ๋ฆฌํ„ฐ๋Ÿด 2๊ฐœ)
โ€ข ์˜ค์ผ๋Ÿฌ ๊ฒฝ๋กœ (๋ชจ๋“  ๊ฐ„์„ ์„ ํ•œ ๋ฒˆ์”ฉ)
โ€ข 2์ƒ‰ ์น ํ•˜๊ธฐ (์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ํŒ๋ณ„)
โ€ข ์ตœ๋‹จ ๊ฒฝ๋กœ
โ€ข ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ
๐Ÿ”ด NP-์™„์ „
โ€ข 3-SAT (์ ˆ๋งˆ๋‹ค ๋ฆฌํ„ฐ๋Ÿด 3๊ฐœ)
โ€ข ํ•ด๋ฐ€ํ„ด ๊ฒฝ๋กœ (๋ชจ๋“  ๊ผญ์ง“์ ์„ ํ•œ ๋ฒˆ์”ฉ)
โ€ข 3์ƒ‰ ์น ํ•˜๊ธฐ
โ€ข ์ตœ์žฅ ๋‹จ์ˆœ ๊ฒฝ๋กœ (๊ฒฐ์ • ๋ฒ„์ „)
โ€ข ์™ธํŒ์› ์ˆœํšŒ

์˜ค์ผ๋Ÿฌ ๊ฒฝ๋กœ๋Š” 1736๋…„ ์˜ค์ผ๋Ÿฌ๊ฐ€ ์พจ๋‹ˆํžˆ์Šค๋ฒ ๋ฅดํฌ ๋‹ค๋ฆฌ ๋ฌธ์ œ์—์„œ ๋ณด์ธ ๋Œ€๋กœ "ํ™€์ˆ˜ ์ฐจ์ˆ˜ ๊ผญ์ง“์ ์ด 0๊ฐœ ๋˜๋Š” 2๊ฐœ์ธ๊ฐ€"(์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„ ๊ธฐ์ค€)๋งŒ ์„ธ๋ฉด ๋๋‚˜. ๊ทธ๋Ÿฐ๋ฐ ๋Œ€์ƒ์ด ๊ฐ„์„ ์—์„œ ๊ผญ์ง“์ ์œผ๋กœ ๋ฐ”๋€Œ๋Š” ์ˆœ๊ฐ„ ๋‹คํ•ญ ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์•Œ๋ ค์ง€์ง€ ์•Š์€ ์˜์—ญ์œผ๋กœ ๋„˜์–ด๊ฐ€ ๋ฒ„๋ ค. 2์™€ 3์˜ ์ฐจ์ด๊ฐ€ ์ด๋ ‡๊ฒŒ ๋ฌด์„œ์šด ๊ฑฐ์•ผ.

๐ŸŽ’ ์˜์‚ฌ ๋‹คํ•ญ ์‹œ๊ฐ„์ด๋ผ๋Š” ๋ฐ˜์ „

๋ฐฐ๋‚ญ ๋ฌธ์ œ๋Š” NP-์™„์ „์ธ๋ฐ, ๋™์  ๊ณ„ํš๋ฒ•์œผ๋กœ O(nW) ์‹œ๊ฐ„์— ํ’€ ์ˆ˜ ์žˆ์–ด(n์€ ๋ฌผ๊ฑด ์ˆ˜, W๋Š” ๋ฐฐ๋‚ญ ์šฉ๋Ÿ‰). "์–ด? ๊ทธ๋Ÿผ ๋‹คํ•ญ ์‹œ๊ฐ„ ์•„๋ƒ?" ์‹ถ์ง€๋งŒ ํ•จ์ •์ด ์žˆ์–ด. ์ž…๋ ฅ ํฌ๊ธฐ๋Š” W๋ผ๋Š” ์ˆซ์ž์˜ ๊ฐ’์ด ์•„๋‹ˆ๋ผ ๊ทธ ์ˆซ์ž๋ฅผ ์ ๋Š” ์ž๋ฆฟ์ˆ˜(๋น„ํŠธ ์ˆ˜)๋กœ ์žฌ๊ฑฐ๋“ . W๊ฐ€ b๋น„ํŠธ๋ฉด ๊ฐ’์€ ์ตœ๋Œ€ ์•ฝ 2แต‡์ด๋ผ, O(nW)๋Š” ์ž…๋ ฅ ํฌ๊ธฐ์— ๋Œ€ํ•ด ์ง€์ˆ˜์ ์ด์•ผ.

์ด๋Ÿฐ ๊ฑธ ์˜์‚ฌ ๋‹คํ•ญ ์‹œ๊ฐ„(pseudo-polynomial time)์ด๋ผ๊ณ  ํ•˜๊ณ , ์ด๋Ÿฐ ๋ฌธ์ œ๋ฅผ ์•ฝํ•œ NP-์™„์ „์ด๋ผ๊ณ  ๋ถˆ๋Ÿฌ. ์ˆซ์ž๊ฐ€ ์ž‘์œผ๋ฉด ์‹ค์ „์—์„œ ๋น ๋ฅด๊ฒŒ ํ’€๋ฆฌ๋‹ˆ ์‹ค๋ฌด์ž์—๊ฒŒ๋Š” ์•„์ฃผ ๋ฐ˜๊ฐ€์šด ์„ฑ์งˆ์ด์•ผ. ๋ฐ˜๋ฉด 3-๋ถ„ํ•  ๋ฌธ์ œ์ฒ˜๋Ÿผ ์ˆซ์ž๊ฐ€ ์ž‘์•„๋„ ์—ฌ์ „ํžˆ NP-์™„์ „์ธ ๊ฒฝ์šฐ๋Š” ๊ฐ•ํ•œ NP-์™„์ „์ด๋ผ๊ณ  ํ•ด.

๐Ÿงฑ 6. ์™œ ์•„๋ฌด๋„ ์ฆ๋ช…ํ•˜์ง€ ๋ชปํ• ๊นŒ: ์„ธ ๊ฐœ์˜ ์žฅ๋ฒฝ

50๋…„ ๋„˜๊ฒŒ ์ˆ˜๋งŽ์€ ์ฒœ์žฌ๊ฐ€ ๋งค๋‹ฌ๋ ธ๋Š”๋ฐ ์™œ ์•„์ง์ผ๊นŒ? ๋‹จ์ˆœํžˆ "์–ด๋ ค์›Œ์„œ"๊ฐ€ ์•„๋‹ˆ๋ผ, ์ง€๊ธˆ๊นŒ์ง€ ์•Œ๋ ค์ง„ ์ฆ๋ช… ๊ธฐ๋ฒ•๋“ค์ด ์›๋ฆฌ์ ์œผ๋กœ ํ†ตํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ๊ฒŒ ์ฆ๋ช…๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด์•ผ. ์ด๊ฒŒ ์ •๋ง ํฅ๋ฏธ๋กœ์šด ๋ถ€๋ถ„์ด์•ผ. ์ˆ˜ํ•™์ด ์Šค์Šค๋กœ ์ž๊ธฐ ๋„๊ตฌ์˜ ํ•œ๊ณ„๋ฅผ ์ฆ๋ช…ํ•œ ๊ฑฐ๊ฑฐ๋“ .

๐Ÿชž ์žฅ๋ฒฝ โ‘  ์ƒ๋Œ€ํ™” (1975)

๋ฒ ์ด์ปค(Baker), ๊ธธ(Gill), ์†”๋กœ๋ฒ ์ด(Solovay)๋Š” 1975๋…„, ์–ด๋–ค ์˜ค๋ผํด(์งˆ๋ฌธํ•˜๋ฉด ํ•œ ๋ฒˆ์— ๋‹ต์„ ์ฃผ๋Š” ๋งˆ๋ฒ• ์ƒ์ž) A๋ฅผ ๋ถ™์ด๋ฉด Pแดฌ = NPแดฌ๊ฐ€ ๋˜๊ณ , ๋‹ค๋ฅธ ์˜ค๋ผํด B๋ฅผ ๋ถ™์ด๋ฉด Pแดฎ โ‰  NPแดฎ๊ฐ€ ๋œ๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์˜€์–ด.

๊ทธ๋Ÿฐ๋ฐ ๋Œ€๊ฐ์„  ๋…ผ๋ฒ•์ด๋‚˜ ์‹œ๋ฎฌ๋ ˆ์ด์…˜์ฒ˜๋Ÿผ ๊ณ„์‚ฐ ๊ธฐ๊ณ„๋ฅผ '๋ธ”๋ž™๋ฐ•์Šค'๋กœ ๋‹ค๋ฃจ๋Š” ๊ธฐ๋ฒ•์€ ์˜ค๋ผํด์„ ๋ถ™์—ฌ๋„ ๋˜‘๊ฐ™์ด ์ž‘๋™ํ•ด. ์ด๋Ÿฐ ์ฆ๋ช…์ด P โ‰  NP๋ฅผ ๋ณด์˜€๋‹ค๋ฉด ๋ชจ๋“  ์˜ค๋ผํด์—์„œ๋„ ์„ฑ๋ฆฝํ•ด์•ผ ํ•˜๋Š”๋ฐ, A๋ผ๋Š” ๋ฐ˜๋ก€๊ฐ€ ์žˆ์ง€. ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ๋„ ๋งˆ์ฐฌ๊ฐ€์ง€. ๊ทธ๋ž˜์„œ ์ƒ๋Œ€ํ™”๋˜๋Š” ์ฆ๋ช… ๊ธฐ๋ฒ•๋งŒ์œผ๋กœ๋Š” P vs NP๋ฅผ ์–ด๋А ์ชฝ์œผ๋กœ๋„ ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†์–ด.

๐ŸŒฟ ์žฅ๋ฒฝ โ‘ก ์ž์—ฐ ์ฆ๋ช… (1994)

๋Œ€๊ฐ์„  ๋…ผ๋ฒ•์ด ๋ง‰ํžˆ์ž ์—ฐ๊ตฌ์ž๋“ค์€ ํšŒ๋กœ ๋ณต์žก๋„, ์ฆ‰ "๋…ผ๋ฆฌ ํšŒ๋กœ๊ฐ€ ์–ผ๋งˆ๋‚˜ ์ปค์•ผ ์ด ํ•จ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‚˜"๋กœ ๋ˆˆ์„ ๋Œ๋ ธ์–ด. ์‹ค์ œ๋กœ ์ œํ•œ๋œ ํšŒ๋กœ(์˜ˆ: ๊นŠ์ด๊ฐ€ ์ผ์ •ํ•œ ACโฐ ํšŒ๋กœ)์—์„œ๋Š” ํŒจ๋ฆฌํ‹ฐ ํ•จ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์—†๋‹ค๋Š” ๋“ฑ์˜ ํ•˜ํ•œ์ด ์ฆ๋ช…๋์ง€.

๊ทธ๋Ÿฐ๋ฐ 1994๋…„ ๋ผ์ฆˆ๋ณด๋กœํ”„(Razborov)์™€ ๋ฃจ๋””์น˜(Rudich)๊ฐ€ ์ฐฌ๋ฌผ์„ ๋ผ์–น์—ˆ์–ด. ๋‹น์‹œ ํšŒ๋กœ ํ•˜ํ•œ ์ฆ๋ช…๋“ค์ด ๊ณต์œ ํ•˜๋Š” '์ž์—ฐ์Šค๋Ÿฌ์šด' ์„ฑ์งˆ์„ ์ •์˜ํ•˜๊ณ , ๊ฐ•๋ ฅํ•œ ์˜์‚ฌ๋‚œ์ˆ˜ ์ƒ์„ฑ๊ธฐ๊ฐ€ ์กด์žฌํ•œ๋‹ค๋ฉด ์ด๋Ÿฐ ์ž์—ฐ ์ฆ๋ช…์œผ๋กœ๋Š” P โ‰  NP๋ฅผ ์ฆ๋ช…ํ•  ์ˆ˜ ์—†๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์˜€๊ฑฐ๋“ . ๋‹ค์‹œ ๋งํ•ด, ์šฐ๋ฆฌ๊ฐ€ ์•”ํ˜ธ๊ฐ€ ์•ˆ์ „ํ•˜๋‹ค๊ณ  ๋ฏฟ๋Š” ๋ฐ”๋กœ ๊ทธ ๊ฐ€์ •์ด ์ด ์ฆ๋ช…๋ฒ•์„ ๋ง‰๊ณ  ์žˆ๋Š” ๊ฑฐ์•ผ. ์•„์ด๋Ÿฌ๋‹ˆํ•˜์ง€? ์ด ์—ฐ๊ตฌ๋กœ ๋‘ ์‚ฌ๋žŒ์€ 2007๋…„ ๊ดด๋ธ์ƒ์„ ๋ฐ›์•˜์–ด.

๐Ÿงฎ ์žฅ๋ฒฝ โ‘ข ๋Œ€์ˆ˜ํ™” (2008)

1990๋…„๋Œ€์—๋Š” IP = PSPACE์ฒ˜๋Ÿผ ์ƒ๋Œ€ํ™” ์žฅ๋ฒฝ์„ ๋„˜์–ด์„  ๊ฒฐ๊ณผ๋„ ๋‚˜์™”์–ด. ๋…ผ๋ฆฌ ์—ฐ์‚ฐ์„ ๋‹คํ•ญ์‹์œผ๋กœ ๋ฐ”๊ฟ” ๋‹ค๋ฃจ๋Š” '์‚ฐ์ˆ ํ™”' ๊ธฐ๋ฒ• ๋•๋ถ„์ด์—ˆ์ง€. ํ•˜์ง€๋งŒ 2008๋…„ ์•„๋ก ์Šจ(Scott Aaronson)๊ณผ ์œ„๊ทธ๋”์Šจ(Avi Wigderson)์€ ์ด ์‚ฐ์ˆ ํ™” ๊ธฐ๋ฒ•์„ ํ™•์žฅํ•œ '๋Œ€์ˆ˜ํ™”'๋ผ๋Š” ํ‹€์„ ์ •์˜ํ•˜๊ณ , ๋Œ€์ˆ˜ํ™”๋˜๋Š” ๊ธฐ๋ฒ•๋„ P vs NP๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†์Œ์„ ๋ณด์˜€์–ด.

๊ทธ๋Ÿผ ๋‚จ์€ ๊ธธ์€? ์„ธ ์žฅ๋ฒฝ์„ ๋ชจ๋‘ ํ”ผํ•˜๋Š” ๊ธฐ๋ฒ•์ด ํ•„์š”ํ•ด. ๋Œ€ํ‘œ์ ์œผ๋กœ ๋Œ€์ˆ˜๊ธฐํ•˜ํ•™๊ณผ ํ‘œํ˜„๋ก ์„ ์ด์šฉํ•˜๋Š” ๊ธฐํ•˜์  ๋ณต์žก๋„ ์ด๋ก (GCT)์ด ๋ฉ€๋ฌผ๋ฆฌ(Ketan Mulmuley)์™€ ์†Œํ˜ธ๋‹ˆ(Milind Sohoni)์— ์˜ํ•ด ์ œ์•ˆ๋์ง€๋งŒ, ์•„์ง P vs NP ํ•ด๊ฒฐ๊ณผ๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ ๋ฉ€์–ด. 2010๋…„ ๋น„๋„ค์ด ๋””์˜ฌ๋ฆฌ์นผ(Vinay Deolalikar)์˜ P โ‰  NP ์ฆ๋ช… ์ฃผ์žฅ์ฒ˜๋Ÿผ ํ™”์ œ๊ฐ€ ๋œ ์‹œ๋„๋„ ์žˆ์—ˆ์ง€๋งŒ, ์ „๋ฌธ๊ฐ€ ๊ฒ€ํ† ์—์„œ ๊ฒฐํ•จ์ด ์ง€์ ๋˜์—ˆ์–ด. ์ง€๊ธˆ๋„ "์ฆ๋ช…ํ–ˆ๋‹ค"๋Š” ์›๊ณ ๊ฐ€ ๊พธ์ค€ํžˆ ๋‚˜์˜ค์ง€๋งŒ ์ธ์ •๋ฐ›์€ ๊ฒƒ์€ ์—†์–ด.

๐Ÿ—ณ๏ธ ์ „๋ฌธ๊ฐ€๋“ค์€ ์–ด๋–ป๊ฒŒ ์ƒ๊ฐํ• ๊นŒ

์œŒ๋ฆฌ์—„ ๊ฐ€์‚ฌํฌ(William Gasarch)๋Š” 2002๋…„, 2012๋…„, 2019๋…„์— ์—ฐ๊ตฌ์ž๋“ค์„ ๋Œ€์ƒ์œผ๋กœ P vs NP ์„ค๋ฌธ์„ ์ง„ํ–‰ํ–ˆ์–ด. 2019๋…„ ์„ค๋ฌธ์—์„œ๋Š” ์‘๋‹ต์ž์˜ ์•ฝ 88%๊ฐ€ P โ‰  NP๋ผ๊ณ  ๋‹ตํ–ˆ์–ด. ๋ฌผ๋ก  ์ˆ˜ํ•™์€ ํˆฌํ‘œ๋กœ ์ •ํ•ด์ง€์ง€ ์•Š์ง€๋งŒ, ๋ถ„์œ„๊ธฐ๋Š” ํ™•์‹คํžˆ ํ•œ์ชฝ์œผ๋กœ ๊ธฐ์šธ์–ด ์žˆ์ง€.

P โ‰  NP๋ฅผ ๋ฏฟ๋Š” ์ด์œ ๋Š” ๋Œ€๋žต ์ด๋ž˜.

๐Ÿ”Ž ๊ฒฝํ—˜์  ์ฆ๊ฑฐ
์ˆ˜์ฒœ ๊ฐœ์˜ NP-์™„์ „ ๋ฌธ์ œ ์ค‘ ๋‹จ ํ•˜๋‚˜๋ผ๋„ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€๋ฆฌ๋ฉด ์ „๋ถ€ ํ’€๋ฆฌ๋Š”๋ฐ, ์ˆ˜์‹ญ ๋…„๊ฐ„ ์•„๋ฌด๋„ ์„ฑ๊ณต ๋ชป ํ–ˆ์–ด.
๐ŸŽจ ์ง๊ด€์  ์ฆ๊ฑฐ
P = NP๋ผ๋ฉด '์ข‹์€ ์ž‘ํ’ˆ์„ ์•Œ์•„๋ณด๋Š” ๋Šฅ๋ ฅ'๊ณผ '์ข‹์€ ์ž‘ํ’ˆ์„ ๋งŒ๋“œ๋Š” ๋Šฅ๋ ฅ'์ด ๊ณ„์‚ฐ์ ์œผ๋กœ ๊ฐ™์•„์ง„๋‹ค๋Š” ์–˜๊ธฐ์•ผ. ์„ธ์ƒ์ด ๊ทธ๋ ‡๊ฒŒ ์ƒ๊ธฐ์ง„ ์•Š์€ ๊ฒƒ ๊ฐ™๊ฑฐ๋“ .
๐Ÿ” ๊ตฌ์กฐ์  ์ฆ๊ฑฐ
์•”ํ˜ธ, ์˜์‚ฌ๋‚œ์ˆ˜ ๋“ฑ ๋งŽ์€ ์ด๋ก ์ด P โ‰  NP๋ณด๋‹ค ๊ฐ•ํ•œ ๊ฐ€์ • ์œ„์—์„œ ์ผ๊ด€๋˜๊ฒŒ ์ž˜ ๋Œ์•„๊ฐ€.

๋ฐ˜๋ฉด ๋„๋„๋“œ ์ปค๋ˆ„์Šค(Donald Knuth)์ฒ˜๋Ÿผ P = NP์ผ ๊ฐ€๋Šฅ์„ฑ์„ ์—ด์–ด ๋‘๋Š” ์ €๋ช…ํ•œ ํ•™์ž๋„ ์žˆ์–ด. ๋‹ค๋งŒ ๊ทธ๋Š” ์„ค๋ น P = NP๋ผ๋„ ๊ทธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‹ค์šฉ์ ์ด์ง€ ์•Š๊ฑฐ๋‚˜ ์กด์žฌ๋งŒ ์ฆ๋ช…๋˜๊ณ  ๊ตฌ์ฒด์ ์œผ๋กœ ์•Œ ์ˆ˜ ์—†์„ ์ˆ˜ ์žˆ๋‹ค๋Š” ์ทจ์ง€๋กœ ๋งํ•œ ๋ฐ” ์žˆ์–ด.

๐ŸŒ 7. ๋งŒ์•ฝ P = NP๋ผ๋ฉด ์„ธ์ƒ์€?

์ƒ์ƒ ๋†€์ด ํ•œ๋ฒˆ ํ•ด๋ณด์ž. ๋ˆ„๊ตฐ๊ฐ€ 3-SAT์„ O(nยฒ)์— ํ‘ธ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐœํ‘œํ–ˆ๋‹ค๊ณ  ์ณ. ๋ฌด์Šจ ์ผ์ด ์ผ์–ด๋‚ ๊นŒ?

๐Ÿ” ์•”ํ˜ธ์˜ ์œ„๊ธฐ

ํ˜„๋Œ€ ์•”ํ˜ธ๋Š” "๋งŒ๋“ค๊ธฐ๋Š” ์‰ฝ๊ณ  ๊ฑฐ๊พธ๋กœ ํ’€๊ธฐ๋Š” ์–ด๋ ค์šด" ์ผ๋ฐฉํ–ฅ ํ•จ์ˆ˜๊ฐ€ ์กด์žฌํ•œ๋‹ค๋Š” ๊ฐ€์ •์— ๊ธฐ๋Œ€. ๊ทธ๋Ÿฐ๋ฐ ์ผ๋ฐฉํ–ฅ ํ•จ์ˆ˜๊ฐ€ ์กด์žฌํ•˜๋ฉด P โ‰  NP๊ฐ€ ๋”ฐ๋ผ ๋‚˜์™€. ๋ฐ”๊ฟ” ๋งํ•˜๋ฉด P = NP์ด๋ฉด ์ผ๋ฐฉํ–ฅ ํ•จ์ˆ˜๋Š” ์กด์žฌํ•  ์ˆ˜ ์—†์–ด. ์—ญํ•จ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋Š” "๋‹ต(์›๋ž˜ ์ž…๋ ฅ)์„ ์ฃผ๋ฉด ํ•จ์ˆ˜๊ฐ’์„ ๊ณ„์‚ฐํ•ด ๋ฐ”๋กœ ๊ฒ€์ฆ"ํ•  ์ˆ˜ ์žˆ์œผ๋‹ˆ NP์— ์†ํ•˜๊ฑฐ๋“ .

๋‹จ, ์ •ํ™•ํžˆ ์งš๊ณ  ๊ฐˆ ์ ์ด ์žˆ์–ด. P โ‰  NP๊ฐ€ ์ฆ๋ช…๋˜๋”๋ผ๋„ ์•”ํ˜ธ๊ฐ€ ์•ˆ์ „ํ•˜๋‹ค๋Š” ๋ณด์žฅ์€ ๋˜์ง€ ์•Š์•„. P โ‰  NP๋Š” ์ตœ์•…์˜ ๊ฒฝ์šฐ์— ๋Œ€ํ•œ ์ด์•ผ๊ธฐ์ธ๋ฐ, ์•”ํ˜ธ๋Š” ๋ฌด์ž‘์œ„๋กœ ๋ฝ‘์€ ํ‰๊ท ์ ์ธ ๊ฒฝ์šฐ์—๋„ ์–ด๋ ค์›Œ์•ผ ํ•˜๊ฑฐ๋“ . ๋˜ ์†Œ์ธ์ˆ˜๋ถ„ํ•ด๋Š” NP์— ์†ํ•˜์ง€๋งŒ NP-์™„์ „์œผ๋กœ ์•Œ๋ ค์ ธ ์žˆ์ง€ ์•Š์•„. ๊ทธ๋ž˜์„œ ์†Œ์ธ์ˆ˜๋ถ„ํ•ด์˜ ์šด๋ช…์€ P vs NP์™€๋Š” ๋ณ„๊ฐœ๋กœ ๊ฒฐ์ •๋  ์ˆ˜๋„ ์žˆ์–ด.

๐Ÿš€ ์ตœ์ ํ™”์™€ ๊ณผํ•™์˜ ํ˜๋ช…

๊ธ์ •์ ์ธ ๋ฉด๋„ ์—„์ฒญ๋‚˜. ๋ฌผ๋ฅ˜ ๊ฒฝ๋กœ, ๋ฐ˜๋„์ฒด ์„ค๊ณ„, ์ผ์ • ๊ณ„ํš, ์‹ ์•ฝ ํ›„๋ณด ํƒ์ƒ‰ ๊ฐ™์€ ์กฐํ•ฉ ์ตœ์ ํ™” ๋ฌธ์ œ๊ฐ€ ํšจ์œจ์ ์œผ๋กœ ํ’€๋ฆด ์ˆ˜ ์žˆ์–ด. ๋” ๊ทน์ ์ธ ๊ฑด ์ˆ˜ํ•™ ๊ทธ ์ž์ฒด์•ผ. "๊ธธ์ด n ์ดํ•˜์˜ ์ฆ๋ช…์ด ์žˆ๋Š”๊ฐ€?"๋Š” NP ๋ฌธ์ œ๋ผ์„œ, P = NP์ด๊ณ  ๊ทธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‹ค์šฉ์ ์ด๋ผ๋ฉด ์ ๋‹นํ•œ ๊ธธ์ด์˜ ์ฆ๋ช…์ด ์กด์žฌํ•˜๋Š” ์ •๋ฆฌ์— ๋Œ€ํ•ด ์ฆ๋ช… ์ฐพ๊ธฐ๊ฐ€ ์ž๋™ํ™”๋  ์ˆ˜ ์žˆ์–ด. ๊ดด๋ธ์ด ํŽธ์ง€์—์„œ ์ƒ์ƒํ–ˆ๋˜ ๋ฐ”๋กœ ๊ทธ ์„ธ๊ณ„์•ผ.

ํ”ํ•œ ์˜คํ•ด: "P = NP๋ฉด ๋ชจ๋“  ๋ฌธ์ œ๊ฐ€ ์ˆœ์‹๊ฐ„์— ํ’€๋ฆฐ๋‹ค" ์•„๋‹ˆ์•ผ! โ‘  ๋‹คํ•ญ ์‹œ๊ฐ„์ด๋ผ๋„ nยนโฐโฐโฐ์ฒ˜๋Ÿผ ์“ธ๋ชจ์—†์„ ์ˆ˜ ์žˆ๊ณ , โ‘ก ์กด์žฌ์„ฑ๋งŒ ์ฆ๋ช…๋˜๊ณ  ๊ตฌ์ฒด์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ชจ๋ฅผ ์ˆ˜๋„ ์žˆ์–ด. โ‘ข ๊ทธ๋ฆฌ๊ณ  NP ๋ฐ”๊นฅ์˜ ๋ฌธ์ œ, ์˜ˆ๋ฅผ ๋“ค์–ด ์ •์ง€ ๋ฌธ์ œ์ฒ˜๋Ÿผ ๊ฒฐ์ • ๋ถˆ๊ฐ€๋Šฅํ•œ ๋ฌธ์ œ๋Š” ์—ฌ์ „ํžˆ ์•„๋ฌด๋„ ๋ชป ํ’€์–ด.

๐Ÿ› ๏ธ 8. ํ˜„์‹ค์˜ ๊ฐœ๋ฐœ์ž๋Š” NP-์™„์ „๊ณผ ์–ด๋–ป๊ฒŒ ์‹ธ์šธ๊นŒ

"์ด ๋ฌธ์ œ๋Š” NP-์™„์ „์ž…๋‹ˆ๋‹ค"๋Š” ๋์ด ์•„๋‹ˆ๋ผ ์ „๋žต์„ ๋ฐ”๊พธ๋ผ๋Š” ์‹ ํ˜ธ์•ผ. ์‹ค์ œ๋กœ ๊ฐœ๋ฐœ ํ˜„์žฅ์—์„œ ์“ฐ๋Š” ๋ฌด๊ธฐ๋Š” ๋‹ค์–‘ํ•ด. ์žฌ๋Šฅ๋„ท ๊ฐ™์€ ํ”Œ๋žซํผ์—์„œ ์ตœ์ ํ™”๋‚˜ ๋ฐ์ดํ„ฐ ๋ถ„์„ ์˜๋ขฐ๋ฅผ ๋ฐ›๋Š” ๊ฐœ๋ฐœ์ž๋ผ๋ฉด, ๋ฌธ์ œ๋ฅผ ๋ฐ›์ž๋งˆ์ž "์ด๊ฒŒ NP-๋‚œํ•ดํ•œ๊ฐ€?"๋ถ€ํ„ฐ ํŒ๋‹จํ•˜๋Š” ์Šต๊ด€์ด ์˜์™ธ๋กœ ํฐ ์ฐจ์ด๋ฅผ ๋งŒ๋“ค์–ด.

๐ŸŽฏ ๋ฌด๊ธฐ โ‘  ๊ทผ์‚ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜

์ตœ์ ํ•ด๋Š” ํฌ๊ธฐํ•˜๊ณ , ์ตœ์ ํ•ด ๋Œ€๋น„ ๋ช‡ ๋ฐฐ ์ด๋‚ด๋ฅผ ๋ณด์žฅํ•˜๋Š” ๋‹ต์„ ๋‹คํ•ญ ์‹œ๊ฐ„์— ์ฐพ๋Š” ์ „๋žต์ด์•ผ.

์ •์  ๋ฎ๊ฐœ: 2-๊ทผ์‚ฌ
์•„์ง ๋ฎ์ด์ง€ ์•Š์€ ๊ฐ„์„ ์„ ํ•˜๋‚˜ ๊ณจ๋ผ ์–‘ ๋์ ์„ ๋ชจ๋‘ ๋„ฃ๋Š” ๊ฒƒ์„ ๋ฐ˜๋ณตํ•˜๋ฉด, ์ตœ์ ์˜ 2๋ฐฐ ์ด๋‚ด๊ฐ€ ๋ณด์žฅ๋ผ. ๊ทน์ ์œผ๋กœ ๊ฐ„๋‹จํ•˜์ง€.
๋ฉ”ํŠธ๋ฆญ TSP: 1.5-๊ทผ์‚ฌ
์‚ผ๊ฐ ๋ถ€๋“ฑ์‹์ด ์„ฑ๋ฆฝํ•˜๋Š” TSP์—์„œ 1976๋…„ ํฌ๋ฆฌ์Šคํ† ํ”ผ๋ฐ์Šค(Christofides) ์•Œ๊ณ ๋ฆฌ์ฆ˜(์„œ๋“€์ฝ”ํ”„๋„ ๋…๋ฆฝ ๋ฐœ๊ฒฌ)์ด 1.5๋ฐฐ๋ฅผ ๋ณด์žฅํ•ด. 2020๋…„ ์นด๋ฅผ๋ฆฐยทํด๋ผ์ธยท์˜ค๋ฒ ์ด์Šค ๊ฐ€๋ž€์ด ์ด๋ฅผ ์•„์ฃผ ๋ฏธ์„ธํ•˜๊ฒŒ ๊ฐœ์„ ํ•œ ๊ฒฐ๊ณผ๋ฅผ ๋ฐœํ‘œํ–ˆ์–ด.
๋ฐฐ๋‚ญ ๋ฌธ์ œ: FPTAS
์›ํ•˜๋Š” ์˜ค์ฐจ ฮต์— ๋Œ€ํ•ด (1โˆ’ฮต)๋ฐฐ ์ด์ƒ์„ n๊ณผ 1/ฮต์— ๋Œ€ํ•œ ๋‹คํ•ญ ์‹œ๊ฐ„์— ์–ป์„ ์ˆ˜ ์žˆ์–ด. ๊ทผ์‚ฌ์˜ '๋ํŒ์™•'๊ธ‰ ๊ฒฐ๊ณผ์•ผ.

๊ทธ๋Ÿฐ๋ฐ ๋ชจ๋“  ๋ฌธ์ œ๊ฐ€ ๊ทผ์‚ฌ์— ๊ด€๋Œ€ํ•˜์ง„ ์•Š์•„. ์‚ผ๊ฐ ๋ถ€๋“ฑ์‹์ด ์—†๋Š” ์ผ๋ฐ˜ TSP๋Š” P โ‰  NP๋ผ๋ฉด ์–ด๋–ค ์ƒ์ˆ˜๋ฐฐ ๊ทผ์‚ฌ๋„ ๋ถˆ๊ฐ€๋Šฅํ•ด. 1990๋…„๋Œ€์˜ PCP ์ •๋ฆฌ๋Š” "์ฆ๋ช…์˜ ๋ช‡ ๋น„ํŠธ๋งŒ ๋ฌด์ž‘์œ„๋กœ ์ฝ์–ด๋„ ๊ฒ€์ฆํ•  ์ˆ˜ ์žˆ๋‹ค"๋Š” ๋†€๋ผ์šด ๊ฒฐ๊ณผ์ธ๋ฐ, ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๋งŽ์€ ๋ฌธ์ œ์˜ ๊ทผ์‚ฌ ํ•œ๊ณ„๊ฐ€ ์ฆ๋ช…๋์–ด. ์˜ˆ๋ฅผ ๋“ค์–ด ์ตœ๋Œ€ 3-SAT์€ ๋ฌด์ž‘์œ„ ๋ฐฐ์ •๋งŒ์œผ๋กœ๋„ ์ ˆ์˜ 7/8์„ ๊ธฐ๋Œ€๊ฐ’์œผ๋กœ ๋งŒ์กฑ์‹œํ‚ค๋Š”๋ฐ, ํ˜ธ์Šคํƒ€๋“œ(Hรฅstad)๋Š” P โ‰  NP๋ผ๋ฉด 7/8๋ณด๋‹ค ์ƒ์ˆ˜๋งŒํผ์ด๋ผ๋„ ๋” ๋‚˜์€ ๊ทผ์‚ฌ ๋น„์œจ์„ ๋ณด์žฅํ•  ์ˆ˜ ์—†๋‹ค๋Š” ๊ฑธ ๋ณด์˜€์–ด. ๋ฌด์ž‘์œ„๋กœ ์ฐ๋Š” ๊ฒŒ ์‚ฌ์‹ค์ƒ ์ตœ์„ ์ด๋ผ๋‹ˆ, ๊ฒธ์†ํ•ด์ง€๋Š” ๊ฒฐ๊ณผ์ง€.

๐Ÿง  ๋ฌด๊ธฐ โ‘ก SAT ์†”๋ฒ„์™€ ํœด๋ฆฌ์Šคํ‹ฑ

์ด๋ก ์ ์œผ๋กœ ์ตœ์•…์€ ์ง€์ˆ˜ ์‹œ๊ฐ„์ด์ง€๋งŒ, ํ˜„๋Œ€ SAT ์†”๋ฒ„๋Š” ์‚ฐ์—… ํ˜„์žฅ์˜ ๋ฌธ์ œ์—์„œ ๋ณ€์ˆ˜ ์ˆ˜๋ฐฑ๋งŒ ๊ฐœ์งœ๋ฆฌ ์‹๋„ ํ’€์–ด๋‚ด๊ณค ํ•ด. ๊ทธ ๋น„๊ฒฐ์ด CDCL(Conflict-Driven Clause Learning)์ด์•ผ. ํƒ์ƒ‰ํ•˜๋‹ค ๋ชจ์ˆœ์— ๋ถ€๋”ชํžˆ๋ฉด, ๋ชจ์ˆœ์˜ ์›์ธ์„ ๋ถ„์„ํ•ด "๋‹ค์‹œ๋Š” ์ด ํ•จ์ •์— ๋น ์ง€์ง€ ๋ง์ž"๋Š” ์ƒˆ ์ ˆ์„ ํ•™์Šตํ•˜๊ณ , ํ•œ์ฐธ ๊ฑฐ์Šฌ๋Ÿฌ ์˜ฌ๋ผ๊ฐ€ ๋‹ค์‹œ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ์‹์ด์ง€.

# DPLL(CDCL์˜ ๋ผˆ๋Œ€) ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋žต
def dpll(clauses, assignment):
    clauses = unit_propagate(clauses, assignment)  # ๋‹จ์œ„ ์ ˆ ์ „ํŒŒ
    if [] in clauses:        # ๋นˆ ์ ˆ = ๋ชจ์ˆœ
        return False
    if not clauses:          # ๋ชจ๋“  ์ ˆ ๋งŒ์กฑ
        return True
    x = choose_variable(clauses)                   # ๋ถ„๊ธฐ ๋ณ€์ˆ˜ ์„ ํƒ
    return (dpll(simplify(clauses, x, True),  assignment | {x: True}) or
            dpll(simplify(clauses, x, False), assignment | {x: False}))

์‹ค์ œ๋กœ SAT ์†”๋ฒ„๋Š” ์นฉ ์„ค๊ณ„ ๊ฒ€์ฆ, ์†Œํ”„ํŠธ์›จ์–ด ๋ฒ„๊ทธ ํƒ์ƒ‰, ์ˆ˜ํ•™ ๋‚œ์ œ ํ•ด๊ฒฐ์—๊นŒ์ง€ ์“ฐ์—ฌ. 2016๋…„ ํ•˜์ผ๋ ˆ(Marijn Heule) ๋“ฑ์€ SAT ์†”๋ฒ„๋กœ '๋ถˆ ํ”ผํƒ€๊ณ ๋ผ์Šค ์„ธ ์Œ ๋ฌธ์ œ'๋ฅผ ํ•ด๊ฒฐํ–ˆ๋Š”๋ฐ, ๊ทธ ์ฆ๋ช… ํŒŒ์ผ์ด ์•ฝ 200ํ…Œ๋ผ๋ฐ”์ดํŠธ์— ๋‹ฌํ•ด ํ™”์ œ๊ฐ€ ๋์–ด.

๊ทธ ๋ฐ–์—๋„ ๋‹ด๊ธˆ์งˆ ๊ธฐ๋ฒ•(simulated annealing), ์œ ์ „ ์•Œ๊ณ ๋ฆฌ์ฆ˜, ํƒ€๋ถ€ ํƒ์ƒ‰ ๊ฐ™์€ ๋ฉ”ํƒ€ํœด๋ฆฌ์Šคํ‹ฑ, ๊ทธ๋ฆฌ๊ณ  ์ •์ˆ˜๊ณ„ํš๋ฒ• ์†”๋ฒ„์˜ ๋ถ„๊ธฐ ํ•œ์ •(branch and bound)์ด ํ˜„์—…์˜ ๋‹จ๊ณจ ๋ฉ”๋‰ด์•ผ. TSP์˜ ๊ฒฝ์šฐ Concorde ์†”๋ฒ„๊ฐ€ 85,900๊ฐœ ๋„์‹œ ์ธ์Šคํ„ด์Šค(pla85900)์˜ ์ตœ์ ํ•ด๋ฅผ ํ™•์ธํ•œ ์‚ฌ๋ก€๋กœ ์œ ๋ช…ํ•˜์ง€.

๐Ÿงฉ ๋ฌด๊ธฐ โ‘ข ํŒŒ๋ผ๋ฏธํ„ฐํ™” ๋ณต์žก๋„

"์ž…๋ ฅ ์ „์ฒด๊ฐ€ ํฌ๋”๋ผ๋„, ์–ด๋–ค ๋งค๊ฐœ๋ณ€์ˆ˜ k๊ฐ€ ์ž‘๋‹ค๋ฉด?"์ด๋ผ๋Š” ๊ด€์ ์ด์•ผ. ์‹คํ–‰ ์‹œ๊ฐ„์ด f(k)ยทn^c ๊ผด์ด๋ฉด FPT(Fixed-Parameter Tractable)๋ผ๊ณ  ํ•ด. ์˜ˆ๋ฅผ ๋“ค์–ด ํฌ๊ธฐ k์˜ ์ •์  ๋ฎ๊ฐœ ์กด์žฌ ์—ฌ๋ถ€๋Š” ๊ฐ„๋‹จํ•œ ๋ถ„๊ธฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ O(2แตยทn) ์ •๋„์— ํŒ์ •ํ•  ์ˆ˜ ์žˆ์–ด. ๊ฐ„์„  (u,v)๋งˆ๋‹ค "u๋ฅผ ๋„ฃ๊ฑฐ๋‚˜ v๋ฅผ ๋„ฃ๊ฑฐ๋‚˜" ๋‘˜ ์ค‘ ํ•˜๋‚˜๋Š” ๋ฐ˜๋“œ์‹œ ํ•ด์•ผ ํ•˜๋‹ˆ, ๊นŠ์ด k์งœ๋ฆฌ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋งŒ ํ›‘์œผ๋ฉด ๋˜๊ฑฐ๋“ . k๊ฐ€ 20 ์ •๋„๋ฉด n์ด ์•„๋ฌด๋ฆฌ ์ปค๋„ ์ถฉ๋ถ„ํžˆ ์‹ค์šฉ์ ์ด์•ผ.

๐Ÿ“ ๋ฌด๊ธฐ โ‘ฃ ํŠน์ˆ˜ ๊ตฌ์กฐ ํ™œ์šฉ

NP-์™„์ „์€ "์ผ๋ฐ˜์ ์ธ ๋ชจ๋“  ์ž…๋ ฅ"์— ๋Œ€ํ•œ ์ด์•ผ๊ธฐ์•ผ. ์ž…๋ ฅ์— ๊ตฌ์กฐ๊ฐ€ ์žˆ์œผ๋ฉด ์‰ฌ์›Œ์ง€๊ธฐ๋„ ํ•ด. ๊ทธ๋ž˜ํ”„ ์ƒ‰์น ์€ ์ผ๋ฐ˜์ ์œผ๋กœ ์–ด๋ ต์ง€๋งŒ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„๋ฉด 2์ƒ‰์œผ๋กœ ๋ฐ”๋กœ ๋๋‚˜๊ณ , ํŠธ๋ฆฌ ์œ„์˜ ๋งŽ์€ NP-๋‚œํ•ด ๋ฌธ์ œ๋Š” ๋™์  ๊ณ„ํš๋ฒ•์œผ๋กœ ์„ ํ˜• ์‹œ๊ฐ„์— ํ’€๋ ค. ํŠธ๋ฆฌ ํญ(treewidth)์ด ์ž‘์€ ๊ทธ๋ž˜ํ”„์—์„œ๋„ ๋น„์Šทํ•œ ์ผ์ด ์ผ์–ด๋‚˜์ง€. ๊ทธ๋Ÿฌ๋‹ˆ ์‹ค๋ฌด์—์„  "๋‚ด ๋ฐ์ดํ„ฐ๋Š” ์–ด๋–ค ๊ตฌ์กฐ์ธ๊ฐ€?"๋ฅผ ๋จผ์ € ๋ณด๋Š” ๊ฒŒ ์ •๋ง ์ค‘์š”ํ•ด.

์‹ค์ „ ์ฒดํฌ๋ฆฌ์ŠคํŠธ: ์–ด๋ ค์šด ๋ฌธ์ œ๋ฅผ ๋งŒ๋‚ฌ์„ ๋•Œ 1๏ธโƒฃ ์ •๋ง ์ตœ์ ํ•ด๊ฐ€ ํ•„์š”ํ•œ๊ฐ€? ์•„๋‹ˆ๋ฉด ๊ทผ์‚ฌํ•ด๋กœ ์ถฉ๋ถ„ํ•œ๊ฐ€?
2๏ธโƒฃ ์ž…๋ ฅ ํฌ๊ธฐ๊ฐ€ ์‹ค์ œ๋กœ ์–ผ๋งˆ๋‚˜ ๋˜๋Š”๊ฐ€? n=20์ด๋ฉด ์ง€์ˆ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ๊ดœ์ฐฎ์„ ์ˆ˜ ์žˆ์–ด.
3๏ธโƒฃ ์ˆซ์ž ๊ฐ’์ด ์ž‘์€๊ฐ€? ์˜์‚ฌ ๋‹คํ•ญ ์‹œ๊ฐ„ DP๊ฐ€ ํ†ตํ•  ์ˆ˜ ์žˆ์–ด.
4๏ธโƒฃ ์ž‘์€ ๋งค๊ฐœ๋ณ€์ˆ˜๊ฐ€ ์žˆ๋Š”๊ฐ€? FPT ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฐพ์•„๋ด.
5๏ธโƒฃ SAT/์ •์ˆ˜๊ณ„ํš๋ฒ• ์†”๋ฒ„์— ๋ชจ๋ธ๋งํ•ด์„œ ๋˜์ ธ๋ณผ ์ˆ˜ ์žˆ๋Š”๊ฐ€?

๐ŸŒŒ 9. P์™€ NP ๋ฐ”๊นฅ์˜ ๋ณต์žก๋„ ์šฐ์ฃผ

๋ณต์žก๋„ ๋™๋ฌผ์›(Complexity Zoo)์ด๋ผ๋Š” ์œ„ํ‚ค๊ฐ€ ๋”ฐ๋กœ ์žˆ์„ ์ •๋„๋กœ ๋ณต์žก๋„ ํด๋ž˜์Šค๋Š” ์ •๋ง ๋งŽ์•„. ํ•ต์‹ฌ ๋ช‡ ๊ฐœ๋งŒ ์†Œ๊ฐœํ• ๊ฒŒ.

ํด๋ž˜์Šค๋œป๋Œ€ํ‘œ ๋ฌธ์ œยท์‚ฌ์‹ค
coNP๋‹ต์ด '์•„๋‹ˆ์˜ค'์ผ ๋•Œ ์งง์€ ์ฆ๊ฑฐ๋กœ ๊ฒ€์ฆ ๊ฐ€๋Šฅ"์ด ๋…ผ๋ฆฌ์‹์€ ํ•ญ์ƒ ์ฐธ์ธ๊ฐ€?"(TAUT). NP = coNP์ธ์ง€๋„ ๋ฏธํ•ด๊ฒฐ
PSPACE๋‹คํ•ญ ํฌ๊ธฐ ๋ฉ”๋ชจ๋ฆฌ๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์–‘ํ™” ๋ถˆ ๋…ผ๋ฆฌ์‹(QBF), ์ผ๋ฐ˜ํ™”๋œ ์ง€์˜ค๊ทธ๋ž˜ํ”ผ ๊ฒŒ์ž„
EXPTIME์ง€์ˆ˜ ์‹œ๊ฐ„์— ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ผ๋ฐ˜ํ™”๋œ nร—n ์ฒด์Šคยท๋ฐ”๋‘‘(ํŠน์ • ๊ทœ์น™ ํ•˜์—์„œ)์€ EXPTIME-์™„์ „
BPP๋ฌด์ž‘์œ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋†’์€ ํ™•๋ฅ ๋กœ ๋งžํžˆ๋Š” ๋‹คํ•ญ ์‹œ๊ฐ„ ๋ฌธ์ œP = BPP๋ผ๊ณ  ๋„๋ฆฌ ์ถ”์ธก๋จ
BQP์–‘์ž ์ปดํ“จํ„ฐ๊ฐ€ ๋‹คํ•ญ ์‹œ๊ฐ„์— ๋†’์€ ํ™•๋ฅ ๋กœ ํ‘ธ๋Š” ๋ฌธ์ œ์†Œ์ธ์ˆ˜๋ถ„ํ•ด(์‡ผ์–ด ์•Œ๊ณ ๋ฆฌ์ฆ˜, 1994)

์•Œ๋ ค์ง„ ํฌํ•จ ๊ด€๊ณ„๋Š” P โІ NP โІ PSPACE โІ EXPTIME์ด์•ผ. ๊ทธ๋ฆฌ๊ณ  ์‹œ๊ฐ„ ๊ณ„์ธต ์ •๋ฆฌ ๋•๋ถ„์— P โ‰  EXPTIME์€ ํ™•์‹คํžˆ ์ฆ๋ช…๋ผ ์žˆ์–ด. ์ฆ‰ ์ € ์‚ฌ์Šฌ ์–ด๋”˜๊ฐ€์—์„œ๋Š” ๋ฐ˜๋“œ์‹œ 'โ‰ '๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฑด๋ฐ, ์ •ํ™•ํžˆ ์–ด๋””์ธ์ง€๋Š” ์•„๋ฌด๋„ ๋ชฐ๋ผ. ๋ชจ๋“  ๊ณ ๋ฆฌ๊ฐ€ ํ•˜๋‚˜์”ฉ ์—ด๋ ค ์žˆ๋Š” ์ˆ˜์ˆ˜๊ป˜๋ผ์•ผ.

โš›๏ธ ์–‘์ž ์ปดํ“จํ„ฐ๊ฐ€ NP-์™„์ „์„ ๊นฐ๊นŒ?

๋งŽ์ด๋“ค ์˜คํ•ดํ•˜๋Š” ์ง€์ ์ด์•ผ. ์‡ผ์–ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์†Œ์ธ์ˆ˜๋ถ„ํ•ด๋ฅผ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€์ง€๋งŒ, ์†Œ์ธ์ˆ˜๋ถ„ํ•ด๋Š” NP-์™„์ „์œผ๋กœ ์•Œ๋ ค์ ธ ์žˆ์ง€ ์•Š์•„. ๊ทธ๋กœ๋ฒ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ N๊ฐœ ์ค‘ ํ•˜๋‚˜๋ฅผ ์ฐพ๋Š” ํƒ์ƒ‰์„ O(โˆšN)์œผ๋กœ ์ค„์—ฌ์ฃผ์ง€๋งŒ, ์ด๊ฑด 2โฟ์„ 2^(n/2)๋กœ ๋ฐ”๊พธ๋Š” '์ œ๊ณฑ๊ทผ ๊ฐ€์†'์ผ ๋ฟ ์—ฌ์ „ํžˆ ์ง€์ˆ˜ ์‹œ๊ฐ„์ด์•ผ. ๊ทธ๋ฆฌ๊ณ  ๋ธ”๋ž™๋ฐ•์Šค ํƒ์ƒ‰ ๋ชจ๋ธ์—์„œ๋Š” ์ด ์ œ๊ณฑ๊ทผ ๊ฐ€์†์ด ์ตœ์„ ์ด๋ผ๋Š” ๊ฒƒ๋„ ์ฆ๋ช…๋ผ ์žˆ์–ด. ๊ทธ๋ž˜์„œ ํ˜„์žฌ ํ•™๊ณ„์˜ ์ผ๋ฐ˜์ ์ธ ์ถ”์ธก์€ "์–‘์ž ์ปดํ“จํ„ฐ๋กœ๋„ NP-์™„์ „ ๋ฌธ์ œ๋ฅผ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€ ์ˆ˜๋Š” ์—†์„ ๊ฒƒ"์ด์•ผ. ๋ฌผ๋ก  ์ด๊ฒƒ๋„ ์ฆ๋ช…๋œ ๊ฑด ์•„๋‹ˆ์•ผ.

๐Ÿ“š 10. ๊ณต๋ถ€ํ•˜๋Š” ์‚ฌ๋žŒ์„ ์œ„ํ•œ ๊ฐœ๋… ์ง€๋„

์—ฌ๊ธฐ๊นŒ์ง€ ๋”ฐ๋ผ์™”๋‹ค๋ฉด ์ •๋ง ๋Œ€๋‹จํ•œ ๊ฑฐ์•ผ! ๋จธ๋ฆฟ์†์„ ์ •๋ฆฌํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•ต์‹ฌ ์—ฐ๊ฒฐ ๊ณ ๋ฆฌ๋ฅผ ํ•œ ๋ฒˆ์— ๋ฌถ์–ด๋ณผ๊ฒŒ.

ํšจ์œจ์„ฑ์˜ ์ฒ™๋„: ์‹คํ–‰ ์‹œ๊ฐ„์„ ์ž…๋ ฅ ํฌ๊ธฐ์˜ ํ•จ์ˆ˜๋กœ ๋ณด๊ณ  ๋น…์˜ค๋กœ ์ฆ๊ฐ€์œจ์„ ๋น„๊ตํ•œ๋‹ค.
๊ฒฝ๊ณ„์„ : ๋‹คํ•ญ ์‹œ๊ฐ„์„ '๋‹ค๋ฃฐ ๋งŒํ•œ(tractable)' ๋ฌธ์ œ์˜ ๊ธฐ์ค€์œผ๋กœ ์‚ผ๋Š”๋‹ค (์ฝ”๋ฒ”โ€“์—๋“œ๋จผ์ฆˆ ๋…ผ์ œ).
๋‘ ํด๋ž˜์Šค: P๋Š” ๋น ๋ฅด๊ฒŒ ํ‘ธ๋Š” ๋ฌธ์ œ, NP๋Š” ๋‹ต์„ ๋น ๋ฅด๊ฒŒ ๊ฒ€์ฆํ•˜๋Š” ๋ฌธ์ œ. P โІ NP.
ํ™˜์›: A โ‰คโ‚š B๋กœ ๋ฌธ์ œ์˜ ์ƒ๋Œ€์  ๋‚œ์ด๋„๋ฅผ ๋น„๊ตํ•œ๋‹ค.
NP-์™„์ „: ์ฟกโ€“๋ ˆ๋นˆ ์ •๋ฆฌ๋กœ SAT๊ฐ€ ์ฒซ NP-์™„์ „ ๋ฌธ์ œ๊ฐ€ ๋˜๊ณ , ์นดํ”„ ์ดํ›„ ์ˆ˜์ฒœ ๊ฐœ๊ฐ€ ํ•ฉ๋ฅ˜ํ•œ๋‹ค.
์žฅ๋ฒฝ: ์ƒ๋Œ€ํ™”ยท์ž์—ฐ ์ฆ๋ช…ยท๋Œ€์ˆ˜ํ™”๊ฐ€ ๊ธฐ์กด ๊ธฐ๋ฒ•์˜ ํ•œ๊ณ„๋ฅผ ๋ณด์—ฌ์ค€๋‹ค.
์‹ค์ „: ๊ทผ์‚ฌ, ํœด๋ฆฌ์Šคํ‹ฑ, SAT ์†”๋ฒ„, FPT, ํŠน์ˆ˜ ๊ตฌ์กฐ๋กœ ์–ด๋ ค์šด ๋ฌธ์ œ์™€ ๊ณต์กดํ•œ๋‹ค.
๋” ๊นŠ์ด ๊ณต๋ถ€ํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด โ€ข ๋งˆ์ดํด ์‹œํ”„์„œ(Michael Sipser), ใ€ŽIntroduction to the Theory of Computationใ€ โ€” ํŠœ๋ง ๋จธ์‹ ๋ถ€ํ„ฐ NP-์™„์ „๊นŒ์ง€ ๊ฐ€์žฅ ์นœ์ ˆํ•œ ์ž…๋ฌธ์„œ.
โ€ข ๊ฐœ๋ฆฌ & ์กด์Šจ, ใ€ŽComputers and Intractabilityใ€ โ€” NP-์™„์ „ ๋ฌธ์ œ ๋ชฉ๋ก์˜ ๊ณ ์ „.
โ€ข ์•„๋กœ๋ผ & ๋ฐ”๋ฝ(Arora & Barak), ใ€ŽComputational Complexity: A Modern Approachใ€ โ€” ์žฅ๋ฒฝ, PCP ์ •๋ฆฌ ๋“ฑ ๊ณ ๊ธ‰ ์ฃผ์ œ๊นŒ์ง€.
ํ˜ผ์ž ๊ณต๋ถ€ํ•˜๋‹ค ๋ง‰ํž ๋• ์žฌ๋Šฅ๋„ท์—์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณผ์™ธ๋‚˜ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฉ˜ํ† ๋ง์„ ์ฐพ์•„๋ณด๋Š” ๊ฒƒ๋„ ๋ฐฉ๋ฒ•์ด์•ผ. ํ™˜์› ์ฆ๋ช…์€ ๋ˆ„๊ตฐ๊ฐ€์™€ ๊ฐ™์ด ์†์œผ๋กœ ๊ทธ๋ ค๋ณด๋ฉด ํ™• ์ดํ•ด๋˜๊ฑฐ๋“ .

๐ŸŽฌ ๋งˆ๋ฌด๋ฆฌ: ์งˆ๋ฌธ ํ•˜๋‚˜๊ฐ€ ๋งŒ๋“  ๊ฑฐ๋Œ€ํ•œ ์ˆฒ

"์ •๋‹ต์„ ํ™•์ธํ•˜๋Š” ๊ฒŒ ์‰ฌ์šฐ๋ฉด, ์ •๋‹ต์„ ์ฐพ๋Š” ๊ฒƒ๋„ ์‰ฌ์šธ๊นŒ?" ์ฒ˜์Œ์—” ์ˆ ์ž๋ฆฌ ์žก๋‹ด์ฒ˜๋Ÿผ ๋“ค๋ ธ๋˜ ์ด ์งˆ๋ฌธ์ด, ์‚ฌ์‹ค์€ ์•”ํ˜ธ์˜ ์•ˆ์ „์„ฑ, ์ตœ์ ํ™”์˜ ํ•œ๊ณ„, ์ˆ˜ํ•™์  ์ฐฝ์˜์„ฑ์˜ ๋ณธ์งˆ๊นŒ์ง€ ๊ฟฐ๋šซ๋Š” ์งˆ๋ฌธ์ด๋ผ๋Š” ๊ฒŒ ๋А๊ปด์ง€์ง€?

P vs NP๋Š” ์•„์ง ํ’€๋ฆฌ์ง€ ์•Š์•˜์ง€๋งŒ, ์ด ๋ฌธ์ œ๋ฅผ ๋ถ™์žก๊ณ  ์”จ๋ฆ„ํ•˜๋Š” ๊ณผ์ •์—์„œ ๊ทผ์‚ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜, ํ™•๋ฅ ์  ๊ฒ€์ฆ, ํšŒ๋กœ ๋ณต์žก๋„, ํ˜„๋Œ€ ์•”ํ˜ธํ•™ ๊ฐ™์€ ์—„์ฒญ๋‚œ ๊ฒฐ๊ณผ๋“ค์ด ์Ÿ์•„์ ธ ๋‚˜์™”์–ด. ์–ด์ฉŒ๋ฉด ์ด ๋ฌธ์ œ์˜ ์ง„์งœ ๊ฐ€์น˜๋Š” ๋‹ต ๊ทธ ์ž์ฒด๋ณด๋‹ค, ๋‹ต์„ ์ฐพ์•„๊ฐ€๋Š” ๊ธธ์—์„œ ํ”ผ์–ด๋‚œ ์ˆ˜๋งŽ์€ ์•„์ด๋””์–ด์— ์žˆ๋Š”์ง€๋„ ๋ชฐ๋ผ. ๊ทธ๋Ÿฌ๋‹ˆ ๋‹ค์Œ์— ์ฝ”๋“œ๊ฐ€ ๋А๋ฆฌ๋‹ค๊ณ  ํˆฌ๋œ๊ฑฐ๋ฆด ์ผ์ด ์ƒ๊ธฐ๋ฉด, ์ž ๊น ๋ฉˆ์ถ”๊ณ  ์ด๋ ‡๊ฒŒ ๋ฌผ์–ด๋ด. "์ด๊ฑด ๋‚ด ์ฝ”๋“œ๊ฐ€ ๋А๋ฆฐ ๊ฑธ๊นŒ, ์•„๋‹ˆ๋ฉด ๋ฌธ์ œ ์ž์ฒด๊ฐ€ ์›๋ž˜ ์–ด๋ ค์šด ๊ฑธ๊นŒ?" ๊ทธ ์งˆ๋ฌธ์„ ๋˜์งˆ ์ˆ˜ ์žˆ๊ฒŒ ๋๋‹ค๋ฉด, ๋„Œ ์ด๋ฏธ ๋ณต์žก๋„ ์ด๋ก ์˜ ์ˆฒ์— ํ•œ ๋ฐœ ๋“ค์–ด์˜จ ๊ฑฐ์•ผ. ๐ŸŒฒ

ํ•ต์‹ฌ ์š”์•ฝ โ€ข ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํšจ์œจ์„ฑ์€ ์ž…๋ ฅ ํฌ๊ธฐ์— ๋”ฐ๋ฅธ ์—ฐ์‚ฐ๋Ÿ‰์˜ ์ฆ๊ฐ€์œจ๋กœ ๋ถ„์„ํ•˜๊ณ , ๋‹คํ•ญ ์‹œ๊ฐ„์ด 'ํšจ์œจ์ '์˜ ์ด๋ก ์  ๊ธฐ์ค€์ด๋‹ค.
โ€ข P๋Š” ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€๋ฆฌ๋Š” ๋ฌธ์ œ, NP๋Š” ๋‹ต์„ ๋‹คํ•ญ ์‹œ๊ฐ„์— ๊ฒ€์ฆํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋‹ค. NP๋Š” "Not Polynomial"์ด ์•„๋‹ˆ๋‹ค.
โ€ข NP-์™„์ „ ๋ฌธ์ œ ํ•˜๋‚˜๊ฐ€ ๋‹คํ•ญ ์‹œ๊ฐ„์— ํ’€๋ฆฌ๋ฉด P = NP๊ฐ€ ๋œ๋‹ค. SAT๊ฐ€ ์ตœ์ดˆ์˜ NP-์™„์ „ ๋ฌธ์ œ๋‹ค(์ฟก 1971, ๋ ˆ๋นˆ 1973).
โ€ข ์ƒ๋Œ€ํ™”(1975)ยท์ž์—ฐ ์ฆ๋ช…(1994)ยท๋Œ€์ˆ˜ํ™”(2008) ์žฅ๋ฒฝ ๋•Œ๋ฌธ์— ๊ธฐ์กด ๊ธฐ๋ฒ•์œผ๋กœ๋Š” ํ•ด๊ฒฐ์ด ์–ด๋ ต๋‹ค๋Š” ๊ฒƒ์ด ์•Œ๋ ค์ ธ ์žˆ๋‹ค.
โ€ข ์‹ค๋ฌด์—์„œ๋Š” ๊ทผ์‚ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜, SAT ์†”๋ฒ„, ํŒŒ๋ผ๋ฏธํ„ฐํ™” ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž…๋ ฅ ๊ตฌ์กฐ ํ™œ์šฉ์œผ๋กœ NP-๋‚œํ•ด ๋ฌธ์ œ์— ๋Œ€์‘ํ•œ๋‹ค.
โ€ข 2000๋…„ ํด๋ ˆ์ด ์ˆ˜ํ•™์—ฐ๊ตฌ์†Œ๊ฐ€ ๋ฐ€๋ ˆ๋‹ˆ์—„ ๋ฌธ์ œ๋กœ ์ง€์ •ํ–ˆ์œผ๋ฉฐ, ์ƒ๊ธˆ 100๋งŒ ๋‹ฌ๋Ÿฌ๋Š” ์•„์ง ์ฃผ์ธ์„ ์ฐพ์ง€ ๋ชปํ–ˆ๋‹ค.
๋Œ“๊ธ€ ์ž‘์„ฑ

์ด ๊ธ€์— ๋Œ€ํ•œ ์—ฌ๋Ÿฌ๋ถ„์˜ ์ƒ๊ฐ์„ ๋“ค๋ ค์ฃผ์„ธ์š”

๋Œ“๊ธ€ 0
๋Œ“๊ธ€์„ ๋ถˆ๋Ÿฌ์˜ค๋Š” ์ค‘์ž…๋‹ˆ๋‹ค.

์•„์ง ๋Œ“๊ธ€์ด ์—†์Šต๋‹ˆ๋‹ค.