Ver5.0 ๐งฉ ๊ณ์ฐ ๋ณต์ก๋ ์ด๋ก ๊ณผ P vs NP ๋ฌธ์ ๋ก ์ฝ๋ ์๊ณ ๋ฆฌ์ฆ์ ํจ์จ์ฑ ๋ถ์

๐งฉ ๊ณ์ฐ ๋ณต์ก๋ ์ด๋ก ๊ณผ P vs NP ๋ฌธ์ ๋ก ์ฝ๋ ์๊ณ ๋ฆฌ์ฆ์ ํจ์จ์ฑ ๋ถ์
"์ ๋ต์ ํ์ธํ๋ ๊ฒ ์ฌ์ฐ๋ฉด, ์ ๋ต์ ์ฐพ๋ ๊ฒ๋ ์ฌ์ธ๊น?" ์ด ํ ์ค์ง๋ฆฌ ์ง๋ฌธ์ 100๋ง ๋ฌ๋ฌ๊ฐ ๊ฑธ๋ ค ์๋ค๋ ๊ฑฐ, ์๊ณ ์์์ด? ์ค๋์ ์น๊ตฌ๋ ์นดํ์์ ์๋ค ๋จ๋ฏ์ด, ์ปดํจํฐ ๊ณผํ์์ ๊ฐ์ฅ ์ ๋ช ํ ๋ฏธํด๊ฒฐ ๋ฌธ์ ๋ฅผ ์ฒ์๋ถํฐ ๋๊น์ง ๊ฐ์ด ๋ฐ๋ผ๊ฐ ๋ณด์.
๋ณต์ก๋ ํด๋์ค์ ํฌํจ ๊ด๊ณ (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ยฒ)์ด๋ผ๊ณ ๋ถ๋ฅด๋ ๊ฑฐ์ง.
๋น ์ค์ ์น์ฒ๋ค๋ ์์๋๋ฉด ์ข์.
๐ ๋คํญ์ vs ์ง์: ๋์ ์ ์๋ ๊ฐ
์ด์ ์ง์ง ์ค์ํ ๊ตฌ๋ถ์ด ๋์. ์ฆ๊ฐ ์๋๋ ํฌ๊ฒ ๋ ๋ถ๋ฅ๋ก ๋๋์ด.
| ๋ณต์ก๋ | ์ด๋ฆ | ๋ํ ์์ | n=10 | n=100 |
|---|---|---|---|---|
| O(1) | ์์ | ๋ฐฐ์ด ์ธ๋ฑ์ค ์ ๊ทผ | 1 | 1 |
| O(log n) | ๋ก๊ทธ | ์ด์ง ํ์ | ์ฝ 3.3 | ์ฝ 6.6 |
| O(n) | ์ ํ | ์ต๋๊ฐ ์ฐพ๊ธฐ | 10 | 100 |
| O(n log n) | ์ ํ ๋ก๊ทธ | ๋ณํฉ ์ ๋ ฌ | ์ฝ 33 | ์ฝ 664 |
| O(nยฒ) | ์ ๊ณฑ | ๋ฒ๋ธ ์ ๋ ฌ | 100 | 10,000 |
| O(nยณ) | ์ธ์ ๊ณฑ | ๋จ์ ํ๋ ฌ ๊ณฑ์ | 1,000 | 1,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๋ง ๋ฒ์ด๋ผ ์ผ๋ฐ ๋ ธํธ๋ถ์ผ๋ก ๋ ๊น์งํ ์ฌ์ด์ ๋๋.
์ค์ ๊ฐ์ผ๋ก ๊ทธ๋ฆฐ ๊ณก์ . ์ด๋ฐ์ 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๊ฐ๋ฅผ ๋ ์ฒ๋ฆฌํ ์ ์์ ๋ฟ์ด์ผ.
๐ค 2. ๊ณ์ฐ์ ์ํ์ผ๋ก: ํ๋ง ๋จธ์ ๊ณผ ๊ฒฐ์ ๋ฌธ์
"๋ฌธ์ ๊ฐ ์ด๋ ต๋ค"๋ฅผ ์ํ์ ์ผ๋ก ์ฆ๋ช ํ๋ ค๋ฉด ๋จผ์ '๋ฌธ์ '์ '๊ณ์ฐ'์ ์ ํํ ์ ์ํด์ผ ํด. ๋ง์ฐํ๊ฒ "์ด๊ฑฐ ์ด๋ ต๋ค~"๋ผ๊ณ ํ๋ฉด ์ํ์๋ค์ด ์ ๋ฐ์์ฃผ๊ฑฐ๋ .
โ ๊ฒฐ์ ๋ฌธ์ : ์/์๋์ค๋ก ๋ตํ๋ ์ง๋ฌธ
๋ณต์ก๋ ์ด๋ก ์ ์ฃผ๋ก ๊ฒฐ์ ๋ฌธ์ (decision problem)๋ฅผ ๋ค๋ค. ๋ต์ด "์" ์๋๋ฉด "์๋์ค"์ธ ์ง๋ฌธ์ด์ผ. ์๋ฅผ ๋ค๋ฉด:
โข "์ด ๊ทธ๋ํ์์ A์์ B๊น์ง ๊ธธ์ด 10 ์ดํ์ธ ๊ฒฝ๋ก๊ฐ ์๋๊ฐ?"
โข "์ด ์ซ์๋ ์์์ธ๊ฐ?"
โข "์ด ์ด๋ ๊ฑฐ๋ฆฌ๊ฐ 1,000km ์ดํ์ธ ์ธํ์ ์ํ ๊ฒฝ๋ก๊ฐ ์๋๊ฐ?"
"์ต๋จ ๊ฒฝ๋ก์ ๊ธธ์ด๋ ์ผ๋ง์ธ๊ฐ?" ๊ฐ์ ์ต์ ํ ๋ฌธ์ ๋, "๊ธธ์ด k ์ดํ์ธ ๊ฒฝ๋ก๊ฐ ์๋๊ฐ?"๋ผ๋ ๊ฒฐ์ ๋ฌธ์ ๋ก ๋ฐ๊ฟ ์ ์์ด. ๊ทธ๋ฆฌ๊ณ k๋ฅผ ์ด์ง ํ์ํ๋ฉฐ ๊ฒฐ์ ๋ฌธ์ ๋ฅผ ์ฌ๋ฌ ๋ฒ ํ๋ฉด ์ต์ ๊ฐ๋ ์ฐพ์ ์ ์์ผ๋, ๊ฒฐ์ ๋ฌธ์ ๋ง ์ฐ๊ตฌํด๋ ๋ณธ์ง์ ๋์น์ง ์์. ํ์์ ์ผ๋ก๋ ๊ฒฐ์ ๋ฌธ์ ๋ฅผ "๋ต์ด '์'์ธ ์ ๋ ฅ ๋ฌธ์์ด๋ค์ ์งํฉ", ์ฆ ์ธ์ด(language)๋ก ๋ด.
โ๏ธ ํ๋ง ๋จธ์ : ๊ณ์ฐ์ ํ์ค ๋ชจ๋ธ
1936๋ ์จ๋ฐ ํ๋ง์ด ์ ์ํ ํ๋ง ๋จธ์ ์ ๋ฌดํํ ํ ์ดํ, ๊ทธ ์๋ฅผ ์์ง์ด๋ ํค๋, ์ ํํ ์ํํ๋ก ์ด๋ค์ง ์์ฃผ ๋จ์ํ ๊ธฐ๊ณ์ผ. ๋จ์ํด ๋ณด์ฌ๋ ์ค๋๋ ์ปดํจํฐ๊ฐ ํ ์ ์๋ ๋ชจ๋ ๊ณ์ฐ์ (์๊ฐ๋ง ์ถฉ๋ถํ๋ค๋ฉด) ํด๋ผ ์ ์๋ค๊ณ ์ฌ๊ฒจ์ ธ. ์ด๊ฒ ์ฒ์นโํ๋ง ๋ ผ์ ์ง.
์ฌ๊ธฐ์ ๋ ์ข ๋ฅ์ ํ๋ง ๋จธ์ ์ด ๋ฑ์ฅํด. ์ด ๊ตฌ๋ถ์ด P์ NP๋ฅผ ๋๋๋ ๊ฒฐ์ ์ ์ด์ ์ผ.
๊ฐ ์ํฉ์์ ๋ค์ ๋์์ด ๋ฑ ํ๋๋ก ์ ํด์ ธ ์์ด. ์ฐ๋ฆฌ๊ฐ ์ฐ๋ ํ๋ฒํ ์ปดํจํฐ๋ ๊ฐ์ ๋ฐฉ์์ด์ผ. ํ ๊ธธ๋ง ์ฑ์คํ ๊ฑธ์ด๊ฐ๋ ์ฐ์ฑ ์.
ํ ์ํฉ์์ ์ฌ๋ฌ ๊ฐ๋๋ก ๋์์ '๋ถ๊ธฐ'ํ ์ ์์ด. ๋ถ๊ธฐ ์ค ํ๋๋ผ๋ '์'์ ๋๋ฌํ๋ฉด ๋ต์ '์'. ๊ฐ๋ฆผ๊ธธ๋ง๋ค ๋ถ์ ์ ์ ์จ์ ๋ชจ๋ ๊ธธ์ ๋์์ ๊ฐ๋ณด๋ ๋์ ๊ฐ์ ์กด์ฌ.
๋น๊ฒฐ์ ๋ก ์ ๊ธฐ๊ณ๋ ์ค์ ๋ก ๋ง๋ค ์ ์๋ ๊ธฐ๊ณ๊ฐ ์๋๋ผ ์ฌ๊ณ ์คํ์ฉ ์ํ์ ๋ชจ๋ธ์ด์ผ. "์ ๋ต์ ๊ธฐ๊ฐ ๋งํ๊ฒ ์ฐ๋ ๋ฅ๋ ฅ์ด ์๋ค๋ฉด?"์ด๋ผ๋ ๊ฐ์ ์ ํ์ํํ ๊ฑฐ์ง.
โ๏ธ 3. P์ NP, ๋๋์ด ์ ์ฒด๋ฅผ ๋ฐํ๋ค
๐ข ํด๋์ค P: ๋น ๋ฅด๊ฒ 'ํ ์' ์๋ ๋ฌธ์ ๋ค
P(Polynomial time)๋ ๊ฒฐ์ ๋ก ์ ํ๋ง ๋จธ์ ์ผ๋ก ๋คํญ ์๊ฐ ์์ ํ ์ ์๋ ๊ฒฐ์ ๋ฌธ์ ๋ค์ ๋ชจ์์ด์ผ. ์ ๋ ฌ, ์ต๋จ ๊ฒฝ๋ก(๋ค์ต์คํธ๋ผ), ์ต๋ ์ ๋, ์ต๋๊ณต์ฝ์ ๊ณ์ฐ ๋ฑ์ด ์ฌ๊ธฐ ์ด์.
P์ ๋ค์ด๊ฐ ์ค ๋ชฐ๋๋ค๊ฐ ๋์ค์ ํ์ธ๋ ์ ๋ช ํ ์ฌ๋ก๋ ์์ด.
๐ต ํด๋์ค NP: ๋น ๋ฅด๊ฒ '๊ฒ์ฆํ ' ์ ์๋ ๋ฌธ์ ๋ค
์, ์ฌ๊ธฐ์ ๊ฐ์ฅ ํํ ์คํด๋ถํฐ ๋ฐ์ด ๋ด๊ณ ๊ฐ์. NP๋ "Not Polynomial(๋คํญ์ด ์๋)"์ ์ฝ์๊ฐ ์๋์ผ! Nondeterministic Polynomial time, ์ฆ "๋น๊ฒฐ์ ๋ก ์ ํ๋ง ๋จธ์ ์ผ๋ก ๋คํญ ์๊ฐ์ ํ ์ ์๋ ๋ฌธ์ "๋ผ๋ ๋ป์ด์ผ.
๊ทธ๋ฐ๋ฐ ์ด ์ ์๋ ์ด๋ ๊ฒ ๋ฐ๊ฟ ๋งํ ์ ์์ด. ํจ์ฌ ์ง๊ด์ ์ด์ผ.
NP = ๋ต์ด '์'์ผ ๋, ๊ทธ๊ฒ์ ๋ท๋ฐ์นจํ๋ ์งง์ ์ฆ๊ฑฐ(์ธ์ฆ์)๊ฐ ์กด์ฌํ๊ณ ,
๊ทธ ์ฆ๊ฑฐ๊ฐ ๋ง๋์ง๋ฅผ ๋คํญ ์๊ฐ์ ํ์ธํ ์ ์๋ ๋ฌธ์ ๋ค์ ๋ชจ์
๋ ์ ์๊ฐ ๊ฐ์ ์ด์ ๋ ๊ฐ๋จํด. ๋น๊ฒฐ์ ๋ก ์ ๊ธฐ๊ณ๊ฐ '์ฐ์' ๋ถ๊ธฐ ๊ฒฝ๋ก ์์ฒด๋ฅผ ์ฆ๊ฑฐ๋ก ์ผ์ผ๋ฉด ๋๊ฑฐ๋ . ๋ฐ๋๋ก ์ฆ๊ฑฐ๊ฐ ์๋ค๋ฉด, ๋น๊ฒฐ์ ๋ก ์ ๊ธฐ๊ณ๋ ์ฆ๊ฑฐ๋ฅผ ํ ๊ธ์์ฉ '์ฐ์ด์' ๋ง๋ ๋ค์ ๊ฒ์ฆํ๋ฉด ๋๊ณ .
์ค๋์ฟ ๋ก ์๊ฐํด ๋ด. ๋น 9ร9 ์ค๋์ฟ ๋ฅผ ํธ๋ ๊ฑด ๋จธ๋ฆฌ๊ฐ ์ํ์ง๋ง, ์น๊ตฌ๊ฐ ๋ค ์ฑ์ด ํ์ ๋ณด์ฌ์ฃผ๋ฉด "๊ฐ๋กยท์ธ๋กยท๋ฐ์ค์ 1~9๊ฐ ํ ๋ฒ์ฉ ์๋?"๋ง ํ์ธํ๋ฉด ๋ผ. ๊ธ๋ฐฉ ๋๋์ง. (์ฐธ๊ณ ๋ก ์ผ๋ฐํํ nยฒรnยฒ ์ค๋์ฟ ๋ NP-์์ ์ด๋ผ๋ ๊ฒ์ด ์ฆ๋ช ๋ผ ์์ด.)
๊ทธ๋ํ 3์ ์น ํ๊ธฐ๋ NP-์์ ๋ฌธ์ . ์ธ์ฆ์(์์น ๊ฒฐ๊ณผ)๋ฅผ ํ์ธํ๋ ๋น์ฉ์ ๊ฐ์ ์์ ๋น๋กํด.
์ ๊ทธ๋ฆผ์์ ์ 7๊ฐ๋ฅผ 3๊ฐ์ง ์์ผ๋ก ์น ํ๋ ๋ฐฉ๋ฒ์ 3โท = 2,187๊ฐ์ง์ผ. ์ ์ด 70๊ฐ๋ฉด 3โทโฐ โ 2.5ร10ยณยณ๊ฐ์ง๊ฐ ๋์ง. ํ์ง๋ง ๋๊ฐ ์์ฑ๋ ์์น ์ ๊ฑด๋ค์ฃผ๋ฉด ์ ํ๋ํ๋์ ์ ๋ ์์ด ๋ค๋ฅธ์ง๋ง ๋ณด๋ฉด ๋์ด์ผ. ๊ฒ์ฆ์ ๊ฐ์ ์๋งํผ, ํ์์ ์ง์๋งํผ. ์ด ๋น๋์นญ์ด NP์ ์ ์ฒด์ผ.
๐ค ๊ทธ๋์ P vs NP ๋ฌธ์ ๋?
P์ ์ํ ๋ฌธ์ ๋ ๋ชจ๋ 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-์์ ๋ฌธ์ ๋จ ํ๋๋ผ๋ ๋คํญ ์๊ฐ์ ํ๋ฆฌ๋ฉด NP ์ ์ฒด๊ฐ P๋ก ๋ฌด๋์ง๊ธฐ ๋๋ฌธ์ด์ผ. ๋ชจ๋ NP ๋ฌธ์ ๊ฐ ๊ทธ ๋ฌธ์ ๋ก ํ์๋๋๊น. ๋ฐ๋๋ก NP-์์ ๋ฌธ์ ํ๋๋ผ๋ ๋คํญ ์๊ฐ์ ์ ํ๋ฆฐ๋ค๋ ๊ฒ ์ฆ๋ช ๋๋ฉด P โ NP๊ฐ ํ์ ๋๊ณ , NP-์์ ๋ฌธ์ ๋ ์ ๋ถ ๋คํญ ์๊ฐ์ ํ ์ ์๊ฒ ๋์ง. ์์ฒ ๊ฐ์ ๋ฌธ์ ๊ฐ ํ ๋ฐฐ๋ฅผ ํ ์ด๋ช ๊ณต๋์ฒด์ธ ์ ์ด์ผ.
๐งจ ์ฟกโ๋ ๋น ์ ๋ฆฌ: ์ฒซ ๋ฒ์งธ NP-์์ ๋ฌธ์
๊ทธ๋ฐ๋ฐ "๋ชจ๋ NP ๋ฌธ์ ๊ฐ ํ์๋๋ค"๋ฅผ ์ฒ์์ ์ด๋ป๊ฒ ์ฆ๋ช ํ์๊น? NP ๋ฌธ์ ๋ ๋ฌดํํ ๋ง์๋ฐ ๋ง์ด์ผ. ์ด ๋ฒฝ์ ์ฒ์ ๋์ ๊ฒ ์ฟกโ๋ ๋น ์ ๋ฆฌ์ผ.
์ฟกโ๋ ๋น ์ ๋ฆฌ์ ์ฆ๋ช ์์ด๋์ด๋ฅผ ๊ฐ๋จํ ๋ง๋ณด์. NP์ ์๋ฌด ๋ฌธ์ ๋ ํ๋ ๊ณ ๋ฅด๋ฉด, ๊ทธ ๋ฌธ์ ๋ฅผ ๋คํญ ์๊ฐ์ ํ์ด๋ด๋ ๋น๊ฒฐ์ ๋ก ์ ํ๋ง ๋จธ์ M์ด ์์ด. M์ด ์ ๋ ฅ x์์ p(n) ๋จ๊ณ ๋์ ์์ง์ด๋ ๋ชจ์ต์ p(n)รp(n) ํฌ๊ธฐ์ ํ(๊ณ์ฐ ๊ธฐ๋ก, tableau)๋ก ๊ทธ๋ฆด ์ ์์ง. ๊ฐ ์นธ์๋ "์๊ฐ t์ ํ ์ดํ ์นธ i์ ๋ฌด์จ ๊ธฐํธ๊ฐ ์๋๊ฐ, ํค๋๋ ์ด๋์ ์๊ณ ์ํ๋ ๋ฌด์์ธ๊ฐ"๊ฐ ๋ค์ด๊ฐ.
์์ ํฌ๊ธฐ๋ ํ ํฌ๊ธฐ์ ๋น๋กํ๋ ๋คํญ์ ํฌ๊ธฐ์ด๊ณ , ๋ง๋๋ ๋ฐ๋ ๋คํญ ์๊ฐ์ด๋ฉด ์ถฉ๋ถํด. ๊ฒฐ๊ตญ "๋ชจ๋ NP ๊ณ์ฐ์ ๋ ผ๋ฆฌ์ ํ๋๋ก ๋ฒ์ญ๋๋ค"๋ ๊ฒ ํต์ฌ์ด์ผ. ๊ณ์ฐ์ด๋ผ๋ ๋์ ์ธ ๊ณผ์ ์ ์ ์ ์ธ ๋ ผ๋ฆฌ ํผ์ฆ๋ก ์ผ๋ ค๋ฒ๋ฆฐ ์ ์ด์ง. ์ฒ์ ๋ฐฐ์ธ ๋ ์๋ฆ ๋๋ ํฌ์ธํธ์ผ.
โ๏ธ ํ์์ ์ฌ์ฌ
SAT๊ฐ ์ฒซ ๋จ์ถ๋ฅผ ๋ผ์ด ๋ค๋ก๋ ์ผ์ด ์ฌ์์ก์ด. ์ ๋ฌธ์ 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-์์ ์ผ๋ก ๊ฐ๋ผ์ง๋ ์๊ฐ์ด์ผ.
โข 2-SAT (์ ๋ง๋ค ๋ฆฌํฐ๋ด 2๊ฐ)
โข ์ค์ผ๋ฌ ๊ฒฝ๋ก (๋ชจ๋ ๊ฐ์ ์ ํ ๋ฒ์ฉ)
โข 2์ ์น ํ๊ธฐ (์ด๋ถ ๊ทธ๋ํ ํ๋ณ)
โข ์ต๋จ ๊ฒฝ๋ก
โข ์ต์ ์ ์ฅ ํธ๋ฆฌ
โข 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๋ฅผ ํด๊ฒฐํ ์ ์์์ ๋ณด์์ด.
๐ณ๏ธ ์ ๋ฌธ๊ฐ๋ค์ ์ด๋ป๊ฒ ์๊ฐํ ๊น
์๋ฆฌ์ ๊ฐ์ฌํฌ(William Gasarch)๋ 2002๋ , 2012๋ , 2019๋ ์ ์ฐ๊ตฌ์๋ค์ ๋์์ผ๋ก P vs NP ์ค๋ฌธ์ ์งํํ์ด. 2019๋ ์ค๋ฌธ์์๋ ์๋ต์์ ์ฝ 88%๊ฐ 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์ด๊ณ ๊ทธ ์๊ณ ๋ฆฌ์ฆ์ด ์ค์ฉ์ ์ด๋ผ๋ฉด ์ ๋นํ ๊ธธ์ด์ ์ฆ๋ช ์ด ์กด์ฌํ๋ ์ ๋ฆฌ์ ๋ํด ์ฆ๋ช ์ฐพ๊ธฐ๊ฐ ์๋ํ๋ ์ ์์ด. ๊ดด๋ธ์ด ํธ์ง์์ ์์ํ๋ ๋ฐ๋ก ๊ทธ ์ธ๊ณ์ผ.
๐ ๏ธ 8. ํ์ค์ ๊ฐ๋ฐ์๋ NP-์์ ๊ณผ ์ด๋ป๊ฒ ์ธ์ธ๊น
"์ด ๋ฌธ์ ๋ NP-์์ ์ ๋๋ค"๋ ๋์ด ์๋๋ผ ์ ๋ต์ ๋ฐ๊พธ๋ผ๋ ์ ํธ์ผ. ์ค์ ๋ก ๊ฐ๋ฐ ํ์ฅ์์ ์ฐ๋ ๋ฌด๊ธฐ๋ ๋ค์ํด. ์ฌ๋ฅ๋ท ๊ฐ์ ํ๋ซํผ์์ ์ต์ ํ๋ ๋ฐ์ดํฐ ๋ถ์ ์๋ขฐ๋ฅผ ๋ฐ๋ ๊ฐ๋ฐ์๋ผ๋ฉด, ๋ฌธ์ ๋ฅผ ๋ฐ์๋ง์ "์ด๊ฒ NP-๋ํดํ๊ฐ?"๋ถํฐ ํ๋จํ๋ ์ต๊ด์ด ์์ธ๋ก ํฐ ์ฐจ์ด๋ฅผ ๋ง๋ค์ด.
๐ฏ ๋ฌด๊ธฐ โ ๊ทผ์ฌ ์๊ณ ๋ฆฌ์ฆ
์ต์ ํด๋ ํฌ๊ธฐํ๊ณ , ์ต์ ํด ๋๋น ๋ช ๋ฐฐ ์ด๋ด๋ฅผ ๋ณด์ฅํ๋ ๋ต์ ๋คํญ ์๊ฐ์ ์ฐพ๋ ์ ๋ต์ด์ผ.
๊ทธ๋ฐ๋ฐ ๋ชจ๋ ๋ฌธ์ ๊ฐ ๊ทผ์ฌ์ ๊ด๋ํ์ง ์์. ์ผ๊ฐ ๋ถ๋ฑ์์ด ์๋ ์ผ๋ฐ 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)์ด ์์ ๊ทธ๋ํ์์๋ ๋น์ทํ ์ผ์ด ์ผ์ด๋์ง. ๊ทธ๋ฌ๋ ์ค๋ฌด์์ "๋ด ๋ฐ์ดํฐ๋ ์ด๋ค ๊ตฌ์กฐ์ธ๊ฐ?"๋ฅผ ๋จผ์ ๋ณด๋ ๊ฒ ์ ๋ง ์ค์ํด.
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. ๊ณต๋ถํ๋ ์ฌ๋์ ์ํ ๊ฐ๋ ์ง๋
์ฌ๊ธฐ๊น์ง ๋ฐ๋ผ์๋ค๋ฉด ์ ๋ง ๋๋จํ ๊ฑฐ์ผ! ๋จธ๋ฆฟ์์ ์ ๋ฆฌํ ์ ์๊ฒ ํต์ฌ ์ฐ๊ฒฐ ๊ณ ๋ฆฌ๋ฅผ ํ ๋ฒ์ ๋ฌถ์ด๋ณผ๊ฒ.
โข ๊ฐ๋ฆฌ & ์กด์จ, ใ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
์ง์์ธ์ ์ฒ - ์ง์ ์ฌ์ฐ๊ถ ๋ณดํธ ๊ณ ์ง
์ง์ ์ฌ์ฐ๊ถ ๋ณดํธ ๊ณ ์ง
- ์ ์๊ถ ๋ฐ ์์ ๊ถ: ๋ณธ ์ปจํ ์ธ ๋ ์ฌ๋ฅ๋ท์ ๋ ์ AI ๊ธฐ์ ๋ก ์์ฑ๋์์ผ๋ฉฐ, ๋ํ๋ฏผ๊ตญ ์ ์๊ถ๋ฒ ๋ฐ ๊ตญ์ ์ ์๊ถ ํ์ฝ์ ์ํด ๋ณดํธ๋ฉ๋๋ค.
- AI ์์ฑ ์ปจํ ์ธ ์ ๋ฒ์ ์ง์: ๋ณธ AI ์์ฑ ์ปจํ ์ธ ๋ ์ฌ๋ฅ๋ท์ ์ง์ ์ฐฝ์๋ฌผ๋ก ์ธ์ ๋๋ฉฐ, ๊ด๋ จ ๋ฒ๊ท์ ๋ฐ๋ผ ์ ์๊ถ ๋ณดํธ๋ฅผ ๋ฐ์ต๋๋ค.
- ์ฌ์ฉ ์ ํ: ์ฌ๋ฅ๋ท์ ๋ช ์์ ์๋ฉด ๋์ ์์ด ๋ณธ ์ปจํ ์ธ ๋ฅผ ๋ณต์ , ์์ , ๋ฐฐํฌ, ๋๋ ์์ ์ ์ผ๋ก ํ์ฉํ๋ ํ์๋ ์๊ฒฉํ ๊ธ์ง๋ฉ๋๋ค.
- ๋ฐ์ดํฐ ์์ง ๊ธ์ง: ๋ณธ ์ปจํ ์ธ ์ ๋ํ ๋ฌด๋จ ์คํฌ๋ํ, ํฌ๋กค๋ง, ๋ฐ ์๋ํ๋ ๋ฐ์ดํฐ ์์ง์ ๋ฒ์ ์ ์ฌ์ ๋์์ด ๋ฉ๋๋ค.
- AI ํ์ต ์ ํ: ์ฌ๋ฅ๋ท์ AI ์์ฑ ์ปจํ ์ธ ๋ฅผ ํ AI ๋ชจ๋ธ ํ์ต์ ๋ฌด๋จ ์ฌ์ฉํ๋ ํ์๋ ๊ธ์ง๋๋ฉฐ, ์ด๋ ์ง์ ์ฌ์ฐ๊ถ ์นจํด๋ก ๊ฐ์ฃผ๋ฉ๋๋ค.
์์ง ๋๊ธ์ด ์์ต๋๋ค.