입력이 이진 인코딩 대신 단 항일 때 강력한 NP-hard 또는 NP-complete 문제 (예 : 여기에 정의 된대로 ) 의 난이도가 변경됩니까?
강력한 NP-hard 문제의 입력이 단항 인코딩되면 어떤 차이가 있습니까? 예를 들어 약한 NP-complete Knapsack 문제를 예로 든다면 바이너리 인코딩시 NP- 완료이지만 단항 인코딩시 동적 프로그래밍으로 다항식 시간으로 해결할 수 있습니다. 다항식 시간 계층의 높은 수준의 경도에 영향을 줄 수 있습니까?
강한 …- 단단한 개념은 다른 복잡한 클래스, 예를 들어 다항식 시간 계층의 상위 클래스에도 적용됩니까?
이전 에 stackoverflow.com 에서이 질문을 했지만 여기에 더 적합하다는 것이 지적되었습니다.
답변
단항으로 인코딩 된 의 문제 크기는 이진 인 경우 크기 과 입니다. 걸린 시간이 이면 첫 번째 경우 이고 두 번째 경우 입니다. 따라서 첫 번째 경우에 다항식 인 알고리즘이 두 번째 경우에는 지수가 될 것입니다. 문제의 인코딩은 알고리즘의 복잡성을 근본적으로 바꿀 수 있습니다.N log N F ( N ) F ( 사이즈 ) F ( 2 사이즈 )
NN
logN
F(N)
F(size)
F(2size)
답변
아니.
입력 인코딩을 변경하면 문제의 공식적인 정의가 변경되었으므로 다른 문제 입니다. 원래 문제의 복잡성은 변하지 않습니다. 같은 이유로 하늘의 다른 빛을 가리 키더라도 달의 질량은 변하지 않습니다.
답변
짧은 대답은 입력이 단항 인코딩되면 더 길다 는 것입니다 . 그것은이다 기하 급수적으로 더 이상. 이제 입력 크기 에서 다항식 시간 으로 작동하는 알고리즘 은 입력 자체가 원래 문제보다 기하 급수적으로 길기 때문에 문제를 해결하기 위해 “충분한 시간”을 갖습니다.