P-NP 문제

P-NP 문제(-問題, 영어: P versus NP problem)는 복잡도 종류 P와 NP가 같은지에 대한 이론 컴퓨터 과학의 미해결 문제로, 간략하게 말해 답을 빠르게 검산할 수 있는 문제는 빠르게 풀릴 수도 있는가를 묻고 있다. 여기서 빠르게라는 말은 다항 시간 안에 작업을 수행하는 알고리즘이 존재한다는 의미로, 즉 걸리는 시간이 알고리즘에 입력하는 크기의 다항함수(이를테면, 지수 함수와 반대)가 된다는 뜻이다. 다항 시간 안에 답을 구하는 알고리즘이 존재하는 문제들을 "P"라고 하며, P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류이다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지는 않지만 답이 제공되었을 때 빠르게 검산하는 것은 가능한데, 다항 시간 안에 답을 검산할 수 있는 문제들을 "NP"라고 한다. NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류이며 "nondeterministic polynomial time"의 약자이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분류가 된다.

P-NP 문제가 해결되면 다항 시간 안에 답을 검산할 수 있는 문제들이 다항 시간 안에 답을 구할 수도 있는지를 알 수 있게 된다. 현재 대부분의 학자들은 P ≠ NP일 것으로 예상하는데, 만약 P ≠ NP인 것으로 드러난다면 NP인 문제들 중에는 풀이법을 확인하는 것보다 답을 구하는 게 더 어려운 경우가 있다는 것을 의미한다. 그러한 문제들은 다항시간 안에 풀 수 없지만 다항시간 안에 답을 검산하는 것은 가능하다.

P-NP 문제는 컴퓨터 과학에서 가장 중요한 미해결 난제이자, 클레이 수학연구소에서 정한 7개의 밀레니엄 문제 중 하나로 100만 달러의 상금이 걸려있다.^[1] 계산 이론에서의 중요성을 차치하고서도, 문제의 증명은 수학, 암호학, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학 등 다양한 분야에 깊은 영향을 끼칠 것으로 예상된다.^[2]

예시

쉽게 풀이법이 확인될 수 있는 문제이지만 답을 구하기는 어려울 수 있는 문제의 예시로는 부분집합 합 문제가 있다. 이 문제는 어떤 정수들의 집합이 주어졌을 때 공집합이 아닌 부분집합 중 적어도 하나 이상의 부분집합의 합계가 0이 될 수 있는지 알아내는 문제이다. 예를 들어 {−2, −3, 15, 14, 7, −10}이라는 집합이 주어졌을 때 이 문제에 대한 답은 그렇다이다. 왜냐하면 부분집합 {-2, -3, -10, 15}의 합계가 0이기 때문이고, 이 부분집합이 문제의 답이 된다는 것을 확인하기 위해서는 3번의 덧셈만으로 충분하다. 반면 처음 주어진 집합에서 원소의 합이 0이 되도록 하는 부분집합을 찾으려면 일일이 부분집합을 만들고, 각 원소들끼리 더하여 0이 되는지 일일이 확인해야 하기 때문에 쉽지 않다. 이러한 조건을 만족하는 부분집합을 다항 시간 안에 찾아내는 알고리즘은 현재까지 알려져 있지 않다. 따라서 부분집합의 합 문제는 NP에 속한다. 만약 P ≠ NP라면 이 문제는 다항 시간 내에 답을 구할 수 없다는 뜻이 된다. 반면 P = NP라면 현재 시간 복잡도(2ⁿ-n-1 회)안에 풀리는 이 문제를, 실제로는 다항시간 안에 풀 수 있는 알고리즘이 존재하며 아직 그러한 알고리즘을 찾지 못했을 뿐이라는 뜻이 된다.

역사

P-NP 문제를 처음 자세히 서술한 것은 1971년 스티븐 쿡의 논문 〈The Complexity of Theorem Proving Procedures〉에서이다.^[3] 엄밀한 정의가 등장한 것은 1971년이지만 그 이전에도 어렴풋하게나마 문제와 그 증명의 어려움, 그리고 잠재적인 결과 등이 언급되었다. 1955년에 수학자 존 내시는 미국 국가안보국에 보낸 편지에서, 충분히 복잡한 암호를 깨기 위해서는 키의 길이에 대해 지수적인 시간이 소요될 것으로 추측하였다.^[4] 또한 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서, 괴델은 현재 Co-NP-완전에 해당하는 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다.^[5]

예상

2002년부터 미국의 컴퓨터 과학자 William Gasarch는 P-NP 문제에 관한 설문을 진행하였다.^[6][7] P ≠ NP일 것으로 예측한 사람은 2002년에 61%, 2012년에 83%, 2019년에 88%로 증가하였다. 전문가로 대상을 한정했을 때에는 P ≠ NP일 것이라고 답한 비율이 99%에 달했다.^[8]

NP-완전

P ≠ NP 또는 P=NP일 때 P, NP, NP-완전, NP-난해 간의 관계를 보여주는 오일러 다이어그램.

 이 부분의 본문은 NP-완전 및 NP-난해입니다.

P-NP 문제에서 중요한 개념 중 하나로 NP-완전이 있는데, NP-완전 문제란 다른 임의의 NP 문제로부터 다항 시간 안에 환원될 수 있는 NP 문제를 말한다. 즉, 모든 NP 문제는 다항 시간 안에 NP-완전인 문제로 변환할 수 있다. 쉽게 표현하자면 NP-완전인 문제는 다른 어떤 NP들보다 해결하기 버거운 축에 속하는 NP 문제이다.

모든 NP 문제만큼은 어려운 문제, 즉 임의의 NP 문제로부터 다항 시간 안에 환원될 수 있는 문제를 NP-난해라고 한다. NP-난해인 문제는 NP에 속할 필요는 없다. 즉 바꾸어 말하면 NP-난해이면서 NP인 문제는 NP-완전 문제에 속한다.

같이 보기

• 수학의 미해결 문제 목록
• 컴퓨터 과학의 미해결 문제 목록
• 게임 복잡도

각주

1. Fortnow, Lance (2009). “The status of the P versus NP problem” (PDF). 《Communications of the ACM》 52 (9): 78–86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. S2CID 5969255. 2011년 2월 24일에 원본 문서 (PDF)에서 보존된 문서. 2022년 12월 4일에 확인함.
2. Fortnow, Lance (2013). 《The Golden Ticket: P, NP, and the Search for the Impossible》. Princeton, NJ: Princeton University Press. ISBN 9780691156491.
3. Cook, Stephen (1971). 〈The complexity of theorem proving procedures〉. 《Proceedings of the Third Annual ACM Symposium on Theory of Computing》. 151–158쪽. doi:10.1145/800157.805047. ISBN 9781450374644. S2CID 7573663.
4. NSA (2012). “Letters from John Nash” (PDF). 2018년 11월 9일에 원본 문서 (PDF)에서 보존된 문서.
5. Hartmanis, Juris. “Gödel, von Neumann, and the P = NP problem” (PDF). 《Bulletin of the European Association for Theoretical Computer Science》 38: 101–107.
6. William I. Gasarch (June 2002). “The P=?NP poll.” (PDF). 《SIGACT News》 33 (2): 34–47. CiteSeerX 10.1.1.172.1005. doi:10.1145/564585.564599. S2CID 36828694. 2007년 6월 15일에 원본 문서 (PDF)에서 보존된 문서.
7. William I. Gasarch. “The Second P=?NP poll” (PDF). 《SIGACT News》 74. 2014년 1월 24일에 원본 문서 (PDF)에서 보존된 문서.
8. “Guest Column: The Third P =? NP Poll1” (PDF). 2019년 3월 31일에 원본 문서 (PDF)에서 보존된 문서. 2022년 12월 6일에 확인함.

참고 문헌

• Cormen, Thomas (2001). 《Introduction to Algorithms》. Cambridge: MIT Press. ISBN 978-0-262-03293-3.
• Garey, Michael; Johnson, David (1979). 《Computers and Intractability: A Guide to the Theory of NP-Completeness》. San Francisco: W. H. Freeman and Company. ISBN 978-0-7167-1045-5.
• Goldreich, Oded (2010). 《P, NP, and NP-Completeness》. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. Online drafts
• Immerman, N. (1987). “Languages that Capture Complexity Classes”. 《SIAM Journal on Computing》 16 (4): 760–778. CiteSeerX 10.1.1.75.3035. doi:10.1137/0216051.
• Papadimitriou, Christos (1994). 《Computational Complexity》. Boston: Addison-Wesley. ISBN 978-0-201-53082-7.