2
모든 NP 문제는 O (2^(n^k)) 일명 EXPTIME으로 해결할 수 있습니까?모든 NP 문제에 대한 상한
여기서 n^k는 입력 크기 n의 다항식 함수이며 문제의 크기에 따라 달라질 수 있습니다. 당신이 솔루션 후보를 가지고 올바른 해결책 여부 다항식 시간에 을 확인할 수있는 경우 (K> = 0)
A
답변
7
문제는 NP에 있습니다. 따라서 하나의 솔루션을 테스트하는 복잡성은 O (n^k)입니다.
후보가 O (n^k) 시간 테스트 할 수 있으므로 O (n^k) 개 이상의 공간을 사용할 수 없습니다.
가능한 후보가 2^(n^k)이므로 각 시간대에 가서 테스트하면 O(2^(n^k) * n^k) 시간이 걸립니다.
이것은 O (2^(n^k))와 동일하다고 생각하지만, 여전히 EXPTIME에 많이 있습니다.
실제로 P-SPACE라는 EXPTIME 하위 클래스에 있습니다.
+2
에 나와있는 것과 같이 순수 이론적 인 질문을 게시하고 싶을 수도 있습니다. 2^(n^k) * n^k = 2^(n k + log2 (n))이 충분하고, n이 충분히 큰 경우에 n = k + k * log2 (n)
지수 시간이있는 경우 전체 검색 공간을 열거 할 수 있습니다. SAT의 경우, 가능한 모든 조합을 시도해 볼 수 있습니다. – senshin
미래에는 [컴퓨터 과학 SE] (http://cs.stackexchange.com/) –