이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
p_np [2011-09-05 07:47] lifthrasiir |
p_np [2016-07-05 10:56] (현재) lifthrasiir 어라 이거 잘못 읽었었네... |
||
---|---|---|---|
줄 19: | 줄 19: | ||
**P** = **NP**와 **[[FP복잡도|FP]]** = **[[FNP복잡도|FNP]]** 문제는 동치이다. 즉 [[결정문제]]를 [[함수문제]]로 바꿔도 상황은 똑같다. | **P** = **NP**와 **[[FP복잡도|FP]]** = **[[FNP복잡도|FNP]]** 문제는 동치이다. 즉 [[결정문제]]를 [[함수문제]]로 바꿔도 상황은 똑같다. | ||
- | 좀 더 비직관적인(?) 예로는, **P** = **NP**와 **[[BPP복잡도|BPP]]** = **P** 중 정확히 하나만이 성립한다는 것이 알려져 있다.(([[http://terrytao.wordpress.com/2008/01/10/distinguished-lecture-series-i-avi-wigderson-the-power-and-weakness-of-randomness-in-computation/|Distinguished Lecture Series I: Avi Wigderson, “The power and weakness of randomness in computation”]])) 이게 뭔 개소리인가 하니, 만약 흔히 생각하는 것대로 **P**가 **NP**랑 다르다면, 확률적인 방법("2/3 확률로 옳은 답을 낸다" 따위)으로 문제를 풀 수 있다면 이걸 정석으로 푸는 방법을 만들 수 있다는(derandomization) 어이 없는 결과가 나온다. (**P**가 **BPP**의 부분집합임은 자명하니까) 어느 쪽이든 상당히 어이 없는 결과인 건 분명하다. | + | 좀 더 비직관적인(?) 예로는, **P** = **NP**와 **[[BPP복잡도|BPP]]** = **P** 중 많아봐야 하나만이 성립한다는 것이 알려져 있다.(([[http://terrytao.wordpress.com/2008/01/10/distinguished-lecture-series-i-avi-wigderson-the-power-and-weakness-of-randomness-in-computation/|Distinguished Lecture Series I: Avi Wigderson, “The power and weakness of randomness in computation”]])) 이게 뭔 개소리인가 하니, 만약 흔히 생각하는 것대로 **P**가 **NP**랑 다르다면, 확률적인 방법("2/3 확률로 옳은 답을 낸다" 따위)으로 문제를 풀 수 있다면 이걸 정석으로 푸는 방법을 만들 수 있다는(derandomization) 어이 없는 결과가 나온다. (**P**가 **BPP**의 부분집합임은 자명하니까) 어느 쪽이든 상당히 어이 없는 결과인 건 분명하다. |
{{tag>수학 전산학 밀레니엄문제}} | {{tag>수학 전산학 밀레니엄문제}} |