| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1999년 2월 1일 월요일 오후 06시 34분 14초 제 목(Title): Re: [질문] NP hard/NP complete P : Polynomial NP : Nondeterministic Polynomial (Nondeterministic Turing Machine에 의해 P time 걸리는 것) (Class of) NP : NP time 만큼 걸리는 문제들의 클래스. problem A (polynomially) transforms to problem B iff 1. A의 instance 에서 B의 instance로 (P time에) 바꾸어 주는 알고리즘 존재. 2. A의 instance = YES iff B의 instance = YES 그러므로 A가 B로 transform 한다면 B의 time complexity는 적어도 A만큼 어렵다. B에 적당한 restriction을 가했더니 A가 되더라.. 그런 종류 얘기. 예를 들면 TSP에서 그래프상 도시간의 거리를 모두 1로 놓고 도시 숫자 n을 restriction으로 놓고 풀면 Hamiltonian Cycle 문제가 된다. TSP 문제를 어떤 시간 T에 풀었다면 HC 푸는데도 T + polynomial time 이면 충분. 그러므로 TSP는 적어도 HC만큼이나 어렵다. NP-complete (class): NP Class에 있는 문제 중 가장 어려운 문제. '71년(?)에 Cook이 Satisfiability(SAT) 문제가 NP클래스의 여느 문제만큼이나 어렵다는거 증명. 그리고 SAT으로부터 transform된 모든 NP 클래스의 문제들도 이 클래스에 속함. 또 다른 NP-complete문제들로부터 P time transformation 이루어지는 모든 NP클래스의 문제들 역시 그만큼이나 어렵고 따라서 NP-complete.(transitive) NP-hard : 우리가 A라는 NP-complete 문제를 알고 있다고 하자. B는 NP클래스인지 그 이상인지 아직 증명이 안되었거나, 그 여부에 상관없이 A => B 라는 tranformation이 성립하면 B는 NP-hard. 그러므로 모든 NP-complete 문제는 NP-hard가 되기도 한다. 즉.. NP 클래스와 NP-hard 클래스 교집합 부분이 NP-complete이라고 보면 된다. 그리고 전산 분야의 가장 큰 Open Problem은 P = NP이냐 아니냐인데, 아닌 것 같으면서도 딱히 증명이 안되어 있음. 만약 P = NP라면 NP-complete 문제의 polynomial time 해가 존재하며 암호 알고리즘들이 다 폴리 타임으로 깨져버림. 대충 이 정도이고 제가 거짓말 한 부분은 다른 분이 수정해 주시겠죠:) --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |