차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

차이 보기로 연결

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>수학 전산학 밀레니엄문제}}

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2016-07-05 10:56 | 작성자 lifthrasiir