P = NP 임이 증명되면 이 세계의 모든 암호체계가 무너진다?!
P는 무엇이고 NP는 무엇인가
P : 컴퓨터가 풀기 쉬운 문제의 집합
NP : 컴퓨터가 검증하기 쉬운 문제의 집합
그러면 "문제를 푼다"라는게 뭘까?
= 정답을 구한다.
정리하자면 NP는 풀기는 어려운데 검증하기는 쉬운 문제의 집합이다.
예를 들면 어떤게 있을까?
1. 비밀번호 맞추기
푸는 방법 : 모든 비밀번호 조합을 넣어본다.
검증 방법 : 정답을 아는 사람에게 물어본다.
2. 스도쿠
푸는 방법 : 모든 칸에 1부터 9사이의 숫자로 조합해서 넣어본다.
검증 방법 : 정답지를 본다.
위 예시 문제들이 왜 풀기 어렵다고 말할 수 있을까? 풀기가 어려운 문제의 정의는 무엇일까?
= input이 커질때 계산 시간이 미친듯이 커지는 것
따라서 비밀번호 맞추기 문제의 경우 비밀번호의 길이가 늘어나면 푸는 계산 시간의 경우가 다항식 시간만큼보다 훨씬 커지기 때문에 풀기가 어려운 문제이다. 그러나 정답인지 검증하는 방법은 정답을 아는 사람에게 물어보면 되기 때문에 굉장히 쉽다. 이런 문제를 NP문제라고 한다.
P와 NP의 관계
✅ P 문제이면 NP 문제인가? = 풀기가 쉬운 문제이면 검증하기 쉬운 문제이다
❓ NP 문제이면 P 문제인가? = 검증하기 쉬운 문제이면 풀기도 쉬운가?
- 컴퓨터가 검증하기 쉬우면 풀기도 쉬운지는 아직 밝혀지지 않았다.
하지만 위 문제가 맞다고 검증된다면 "이 세상의 모든 암호체계"가 무너지게 된다. - 위 예시로 비밀번호 맞추기가 NP 문제인데 이 문제가 P라는게 증명되면, 비밀번호 맞추기는 쉽다가 되기 때문에 세상 모든 비밀번호는 뚫리게 된다.
P (Polynomial Time) 클래스는 결정론적 튜링 기계(Deterministic Turing Machine, DTM)가 다항 시간(polynomial time) 내에 해결할 수 있는 문제들의 집합이다. 즉, 어떤 입력 크기 n에 대해, 최악의 경우에도 𝑂(𝑛^𝑘) 시간 내에 해결할 수 있는 문제들을 의미한다.
NP는 비결정론적 튜링 기계(Nondeterministic Turing Machine, NTM)에서 다항 시간 내에 해결할 수 있는 문제들의 집합이다. NP 문제의 더 중요한 특징은 "주어진 해(solution)가 다항 시간 내에 검증될 수 있다"는 점이다.
