컴퓨터 과학의 미해결 문제 목록: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 Robot: Automated text replacement (-{{토막글|전산학}} +{{토막글|컴퓨터 과학}}) |
잔글 로봇이 바꿈: en:List of unsolved problems in computer science; 예쁘게 바꿈 |
||
2번째 줄:
== 계산복잡도 이론 ==
=== [[P-NP 문제]] ===
* '''출처'''
** [[스티븐 쿡]]과 [[레오니드 레빈]]
** ''Proceedings of the 3rd Annual ACM Symposium on Theory of Computing'' (1971), pp. 151--158.
* '''설명''': [[P (복잡도)|P]]는 [[다항시간]]에 풀 수 있는 문제들의 집합이고, [[NP (복잡도)|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-완전]] 문제들에 대한 효율적으로 풀 수 있는 방법이 존재하지 않는다는 것이 증명된다.
11번째 줄:
== 암호학 ==
=== [[일방향함수]]는 존재하는가? ===
* '''출처'''
** [[휘트필드 디피]], [[마틴 헬만]]
** ''IEEE Trans. Inform. Theory'', IT-22, 6, 1976, pp.644-654
** [http://citeseer.ist.psu.edu/340126.html Online copy (HTML)]
* '''설명''': 일방향 함수는 계산하기는 쉽지만 역을 구하는 것은 어려운 함수이다. 일부에서는 [[이산 로그]]를 계산하는 것이나 [[RSA 암호|RSA]]의 역을 구하는 것이 일방향함수일 것이라고 예측하고 있다.
* '''의미''': 일방향 함수가 존재한다면 안전한 [[공개열쇠암호]]를 만들 수 있다. 또한 일방향 함수가 존재한다면 P와 NP가 같지 않다는 증거가 된다.
25번째 줄:
[[분류:전산학의 미해결 문제|*]]
[[en:
[[es:Problemas no resueltos de la informática]]
[[ja:計算機科学の未解決問題]]
| |||