NP-Complete1 P-NP 문제(P-NP problems) P: deterministic Polynomial time NP: Non-deterministic Polynomial time Polynomial time이란 수식으로 표현할 수 있는, 즉 유한한 시간이라는 의미이다. P: 풀기 쉽고 답이 맞는지 확인하기 쉬운 문제들이다. NP: 풀기는 어렵지만 답이 있다면 답이 맞는지 검증하기는 쉬운 문제들이다. 예) 스도쿠 NP-hard: 변환(transform), 축소(reducing) 기법들을 이용해서 NP 문제를 또 다른 형태로 변경시킨 것이다. 아직 NP인지 P인지 조차 알 수 없는 경우에 해당한다. 이런 이유로 다이어그램에서 점선으로 표시하였다. NP-Complete: 변환 또는 축소 기법으로 NP문제를 다른 형태로 변경시킨 경우이다. 다만 이 경우에는 변경.. 2021. 3. 30. 이전 1 다음
