소수 판별 문제는 verification도 어렵자나?
근데 왜 NP에 속해?
소수 판별 문제는 verification도 어렵자나?
근데 왜 NP에 속해?
[일반] 소수판별 문제가 왜 NP에 속하는 문제야??
익명(211.36)
2018-06-16 02:54
추천 0
소수 판별 문제는 verification도 어렵자나?
근데 왜 NP에 속해?
댓글 11
다른 게시글
-
오늘의 알고리즘 뻘짓 [3][일반] 익명(221.153) | 18.06.16추천 0
-
지금 너무 못한다고 실망하지 말아라 [6][일반] 0xrgb(0xrgb) | 18.06.16추천 1
-
졸업한 취준생 참가할수있는대회는 코드포스뿐? [11][일반] 익명(221.153) | 18.06.16추천 0
-
대회 참가할때 가장 어려운건 팀이름 짓기임 [8][일반] 0xrgb(0xrgb) | 18.06.16추천 0
-
요즘 초딩들 웰케똑똑하냐 [1][일반] 익명(221.153) | 18.06.16추천 0
-
koi는 또 뭐야? [8][일반] 익명(118.218) | 18.06.15추천 0
-
KOI 금상 타기 어려움? [5][일반] 익명(39.121) | 18.06.15추천 0
-
카카오에서 대회연다던데 [7][일반] 익명(223.62) | 18.06.15추천 0
-
질문이 있어유 [4][일반] 00가나(221.157) | 18.06.15추천 0
-
알고리즘 문제 사이트 어디가 젤조음여?? [6][일반] 익명(175.223) | 18.06.15추천 0
어떤 수가 소수인지 찾는건 O(sqrt(n))
AKS 켜라
https://en.wikipedia.org/wiki/AKS_primality_test
참고로 이런 문제에서 polynominal 이라는 뜻은 N이 입력의 크기가 아니라 N비트라는 뜻임
따라서 O(sqrt(N))은 실제로는 O(sqrt(2^N)) = O(1.4^N)
참고로 실제로는 다들 Miller-Rabin이라는 ㄱㅆㅆㅌㅊ 알고리즘을 씀. 이 알고리즘은 확률적 알고리즘인데, 판별하려는 소수가 작을때는 deterministic 하게 판별 가능함
밀러 라빈 알고리즘은 사실상 소수를 거의 1에 가까운 정확도로 찾아낼 수 있음. 개사기 알고리즘임
그럼 AKS를 이용하면 verify가 쉬워지는거지?
소수판별은 P이면서 NP임
그냥 verify 같은거 할 필요 없이 AKS 이용해서 답구해서 비교하면 되잖어
아 ㄱㅅㄱㅅ