컴퓨터 과학의 미해결 문제 목록

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

계산복잡도 이론

P-NP 문제

• 출처
  • 스티븐 쿡과 레오니드 레빈
  • 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가 일방향 함수일 것이라고 추정하고 있으나, 아직까지 증명된 것은 없다.