전산학의 미해결 문제

다음은 전산학의 주요 미해결 문제를 정리한 것이다. 이 문제의 해답이 밝혀지면 관련분야에 큰 파급효과를 미칠 것이다.

[편집] 계산복잡도 이론

출처
- 스티븐 쿡과 레오니드 레빈
- Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.
설명: P는 다항시간에 풀 수 있는 문제들의 집합이고, NP는 다항시간에 검증할 수 있는 문제들의 집합이다. P에 속하는 문제는 당연히 NP에 속한다. P-NP 문제는 'NP가 P에 속하는가', 즉 'P와 NP의 집합이 같은가'는 문제이다. One can see the question as a specific case of the problem in proving lower bounds for computational problems.
의미: P와 NP가 같다면, 오늘날까지 어려울 것으로 예상했던 문제들을 빠르게 풀 수 있다. 만약 P와 NP가 다르다면, NP-완전 문제들에 대한 효율적으로 풀 수 있는 방법이 존재하지 않는다는 것이 증명된다.
예상: 스티븐 쿡과 레오니드 레빈이 NP-완전의 개념을 발견한 이후에는 거의 의미있는 진전이 없는 상태이지만, 보통 P와 NP는 다를 것으로 추정한다.

일방향함수는 존재하는가?

출처
- 휘트필드 디피, 마틴 헬만
- IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654
- Online copy (HTML)
설명: 일방향 함수는 계산하기는 쉽지만 역을 구하는 것은 어려운 함수이다. 일부에서는 이산 로그를 계산하는 것이나 RSA의 역을 구하는 것이 일방향함수일 것이라고 예측하고 있다.
의미: 일방향 함수가 존재한다면 안전한 공개열쇠암호를 만들 수 있다. 또한 일방향 함수가 존재한다면 P와 NP가 같지 않다는 증거가 된다.
예상: 이산 로그나 RSA가 일방향 함수일 것이라고 추정하고 있으나, 아직까지 증명된 것은 없다.