| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Pabochet) 날 짜 (Date): 2003년 1월 4일 토요일 오후 09시 35분 42초 제 목(Title): Re: NP가 아닌 알고리즘도 있나요? 엄.... 엄청나게 많이 있습니다. 2^N, 2^2^N, 2^2^2^N등등 의 시간이 걸리는 것들이 다 있다고 증명이 되어 있고 이 중 2^N은 NP하고 같은지 다른지 모르지만 (다르다고 믿기는 함), 나머지들은 다 다르다는 것이 증명이 되어 있습니다. 이런 증명에 사용되는 방법들이 상당히 '인공적'이라는 느낌을 주는 것이라, 자연스러운 문제는 별로 없습니다만.... 좀 실감이 나는 예는 다음과 같은 것이 있기는 합니다. P U 2^N U 2^2^N U 2^2^2^N U ... 을 ELEMENTARY라고 부릅니다. 즉, ELEMENTARY는 polynomial, 지수, 2차지수, 3차지수...의 시간에 풀수 있는 문제들의 집합입니다. 사실 지수시간이 걸리면 안풀리는 것이라고 봐야 하니 ELEMENTARY는 엄청나게 어려운 문제들을 다 포함하고 있다고 봐야지요. Regular Expression 문제는 Unix 써보신 분들은 다 아는 문제일 테지만, Regular Expression 문제를 NOT 연산자 까지 포함하도록 하면 ELEMENTARY 밖에 있다는 것이 증명이 된다 합니다. 지금까지 한 얘기는 얼마나 어려운 것들이 '멀리' 있는가 하는 거였구요, 난이도 계층들이 얼마나 촘촘한가 하는 것도 연구가 되어 있습니다. 이건 hierarchy theorem 정도로 search를 해보시면 나올래나.... |