| [ QuizWit ] in KIDS 글 쓴 이(By): chopin (** 쇼팽 **) 날 짜 (Date): 2003년 1월 4일 토요일 오후 07시 38분 52초 제 목(Title): Re: NP가 아닌 알고리즘도 있나요? 찾아보니 NP-hard의 대표로 halting problem이 있더군요. 이것은 undecidable한 경우니까 당연히 NP가 아닌건 알겠습니다. 그런데 decidable한 문제들 중에서 NP가 아닌 문제들도 있습니까? 답이 확실하게 존재한다면 상식적으로 nondeterministic하게 답을 찾아 써치해 나간다면 polynomial time에 존재하는 답에 도달하지 못하는 답이 있다는거는 상상하기 어려운데요. NP-hard는 decision problem이 아니고 보통의 경우 최대/최소값등을 찾는 식의 일반해를 찾는 문제입니다. 질문을 다시 바꿔보면 다음과 같습니다. "decidable한 decision problem중에서 NP가 아닌 문제가 있는가?" __ 쇼팽 http://mobigen.com/~chopin |