| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1998년02월14일(토) 15시45분07초 ROK 제 목(Title): Re: RRe: NP problem Definition에 관한 박종대님의 정정 감사합니다. 위에 에딧하여 고쳐두었고. 그리고 Longest Common Subsequence 문제는 NP-hard 문제 맞습니다. G&J 책 보면 228쪽 SR10번 문제로 나옵니다. Shortest Common Superstring, Shortest Common Supersequence, Longest Common Subsequence 전부다 NP-hard 문제로 나와있네요. 그런데 Longest Common Subsequence 중 K가 고정이거나 |R|이 고정이면 polynomial time으로 풀린답니다. (인스턴스에 대한 것은 책 참조) Longest Common Substring 문제는 쉽게 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 | ~ | @@ ~ @@ |