2014-09-15 6 views
2

knapsack problemO(n²V) 시간에 풀릴 수 있습니다. 여기서 V = max(v[i], i = 1,..,n)은 항목의 최대 값을 나타냅니다. 반올림 매개 변수 θ = ε/n * V으로 "단위 변경"을 수행하고 수정 된 값인 y[i] = ceil(v[i]/θ)을 고려하면 에 대한 실행 시간은 O(n³/ε)이며ε > 0으로 고정됩니다. 존 클라인 버그에 의해 도서 알고리즘 디자인에서 배낭의 다항식 시간 근사

, 그들은 상태 다음 실행 시간이 1/ε보다는 log 1/ε 포함으로 원하는 정밀도 ε

의존성은 다항식 없습니다. 모든

첫째, 용어 의사 다항식 뒤에 전체 아이디어는 내가 그것에 대해 몇 가지 기사를 읽었습니다에도 불구하고, 나에게 정확하게 명확하지 않다. 그러나이 지식 격차 외에도 주로 실행 시간에 1/ε 대신 log 1/ε이 포함될 경우 ε에 대한 종속성이 다항식이되는 이유를 스스로 묻습니다.

답변

1

문제가 다항식 시간인지 여부는 인스턴스가 인코딩되는 방법에 따라 다릅니다. 예를 들어, PADDED-SATISFIABILITY 문제를 정의 할 수 있습니다. 유효한 인스턴스는 n 개의 변수와 2^n 개의 정크 비트가있는 부울 수식으로 구성됩니다. 패딩 덕택에, PADDED-SATISFIABILITY는 다항식 시간에서 풀 수 있습니다 (아마, SATISFIABILITY와는 달리 NP 하드).

인스턴스에 정수가 관련된 경우 양수를 나타내는 데 사용되는 비트 수가 해당 정수의 log2에 해당하는 인코딩을 사용하는 것이 일반적입니다. A pseudo-polynomial-time 알고리즘은 양수의 이진 표현에서 단항으로 전환하여 기하 급수적으로 (!) 더 많은 비트가 표현되도록 요구하는 경우 알고리즘이 다항식 - 시각.

1/ε이 양의 정수라고 가정하면 Kleinberg는 다항식 의존도가 로그 1/ε에있을 것이라는 점을 지적합니다. 이는 대략 다음을 지정하는 데 필요한 비트 수이기 때문입니다. 매개 변수는 2 진수입니다. 단항 표현의 비트 수는 대략 1/ε이 될 것이다.

+0

'log 1/ε'은 대략 2 진수로 '1/ε'을 저장하는 데 필요한 비트 수입니다. - 나에게 절대적으로 명확하지만, 왜 문제가됩니까? 'O (n^k)'의'n '에 대해서도 같은 방식으로 논할 수는 없었습니까? 'n'이 단지 루프 카운터 일지라도, (일반적으로) 그 값을 저장해야합니다. 그래서'n '을'1/ε'과 다른 점은 무엇입니까? [또한, 왜 어떤 매개 변수의 단항 표현을 고려할 것입니까?] – 0xbadf00d

+0

@ 0xbadf00d 'n'이 목록의 요소의 개수라면, 목록 요소 자체는 선형 비트 수를 사용하여 정렬합니다 무의미한 'n'표현 방법. 'n '이 단지 숫자 일 경우 (예를 들어, 팩토링을 위해), 그것은'1/ε '과 같은 방식으로 취급됩니다. –

+0

@ 0xbadf00d 단항 표현에 대해 생각하는 이유는 의사 - 다항식 시간이 공식적으로 정의되는 방식이기 때문입니다. 사람들은 Stack Overflow에서 배낭 변형에 대해 자주 묻습니다. 의견이나 답변 중 하나는 "NP가 힘들고 운이 없다"는 것입니다. 그러나 배낭은 약하게 NP 하드이기 때문에, 작은 정수 입력에서 잘 작동하는 알고리즘이 존재하며, 이는 실제로 매우 유용합니다. 반면에 [3-partition] (http://en.wikipedia.org/wiki/3-partition_problem)은 작은 정수 입력이 더 쉽지 않습니다. –