카테고리 없음 P, NP, NP-hard, NP-Complete JChori 2011. 12. 2. 14:34 http://meneng2.tistory.com/83 P, NP, NP-hard, NP-Complete class/Algorithm 알고리즘 수업시간에 배운 NP 관련 용어들 정리. P = set of decision problems that can be solved in polynomial time of the input bit size by a TM NP = set of problems for which any yes instance has some proof so that the instance can be fverified to be yes in polynomial time. NP-Hard = if all problems R ∈ NP are reducible to Q, then Q is NP-Hard NP-Complete = Q is NP-Complete if Q is NP-Hard and Q ∈ NP P D. 다항시간에 풀 수 있는 문제 *다항시간? 변수에 붙은 지수가 상수인 형태의 공식으로 나타낼 수 있으면 다항시간이라고 한다. NP D1. NP 는 정답(yes instance) 이 있는 경우, 다항시간에 문제가 맞는지 틀리는지를 확인 할 수 있는 문제. D2. NDTM (None-deterministic Turing Machine) 에 의해서 다항시간에 검증 될 수 있는 문제. *D1 과 D2 는 equivalent 하다. NP-Complete NP-Hard D 모든 경우의 수를 확인해보는 방법 이외에 달리 해결 할 수 있는 방법이 없는 문제 (http://www.aistudy.co.kr/computer/np_hard.htm need more study...) NP-Complete NP에 속하면서 NP-Hard 인 문제 사진 출처 : http://en.wikipedia.org/wiki/NP-complete P=NP 인가에 대한 결과에 따라서 두가지로 나누어지는 문제들간의 관계들 공유하기 게시글 관리 순간을 이어 영원으로. 저작자표시 비영리 변경금지 (새창열림)
