The tower of light

지수시간문제는 모두 NP인가?

  막연하게 알고리즘을 배울때 NP problem 은 그냥 풀기 어려운 문제 라고만 생각을 했고 정확한 그 정의와
의미는 알지 못했다.

대학원 전공면접을 준비하면서 족보를 보던중 저 질문이 있었다. 지수시간이 걸리는 문제라... 흠...
시간이 그렇게 많이 걸린다면 어려운 문제이니 NP problem이 아닐까???

정의부터 다시 찾아보고 이것저것 공부를 해보니 결론은
모든 지수시간문제가 NP problem은 아니다.  였다.


다음은 하노이 탑의 문제의 시간 복잡도(Time complexity)를 분석한 것이다.



위에서 보는 바와 같이 하노이 탑 문제는 지수시간 문제이다. 하지만 NP problem은 아니다. 왜???

그건 NP problem의 정의에서 찾을 수 있다.

NP Problem 정의
Non-deterministic algorithm에 의해 Polynomial time안에 풀 수 있는 decision problem들의 집합
( 또 다른 정의로는 Deterministic algorithm을 사용하여 그 해답을 검증하는데 Polynomial time
   시간이 걸리는 문제들의 집합 )

  그리니깐 그 해답이 맞는지 검증하는데 polynomial time이 걸려야 하는데 이 하노이 탑의 경우 2^n - 1 번의
시간이 흘러야만 검증 할 수 있으므로 NP problem이 아니다.