강력한 NP 완전성

Strong NP-completeness

계산 복잡도에서 강한 NP 완전성은 NP 완전성의 특수한 경우인 계산 문제의 속성입니다.일반적인 계산 문제에는 수치 파라미터가 있을 수 있습니다.예를 들어, 빈 패킹 문제에 대한 입력은 특정 크기의 객체와 객체를 포함해야 하는 빈의 크기 목록입니다. 이러한 객체 크기와 빈 크기는 숫자 매개 변수입니다.

입력 [1]길이의 다항식에 의해 모든 수치 파라미터가 경계가 되어도 NP-완전(강력한 의미에서 NP-완전)이 유지된다면 문제는 강하게 NP-완전(NP-완전)이라고 한다.어떤 문제는 강한 NP-완전 문제가 다항식 감소를 갖는다면 강한 NP-hard라고 한다. 특히 조합 최적화에서는 "strongly NP-hard"라는 문구는 다른 강한 NP-완전 문제로 다항식 감소를 갖는 것으로 알려져 있지 않은 문제에 대해 남겨진다.

일반적으로 문제에 대한 수치 파라미터는 위치표기로 제공되므로 입력크기 n의 문제에는 n의 크기가 지수인 파라미터가 포함될 수 있습니다.단항 표기로 지정된 파라미터를 가지도록 문제를 재정의하는 경우 파라미터는 입력 크기로 제한되어야 합니다.따라서 강한 NP-완전성 또는 NP-강도는 문제의 이 단항 버전의 NP-완전성 또는 NP-강도로 정의될 수도 있습니다.

예를 들어, 빈 패킹은 NP-완성이 강한 반면 0-1 Knapsack 문제는 NP-완성이 약합니다.따라서 객체와 빈 크기가 다항식으로 묶인 정수인 빈 패킹 버전은 NP-완전 상태로 유지되는 반면, 냅색 문제의 해당 버전은 동적 프로그래밍에 의해 의사 다항식 시간에 해결될 수 있습니다.

이론적인 관점에서 다항식 경계 목적 함수의 강한 NP-하드 최적화 문제는 P = [2]NP가 아닌 한 완전한 다항식 시간 근사 체계(또는 FPTAS)를 가질 수 없다.[3] 그러나, 역행은 실패한다. 예를 들어 P가 NP와 같지 않은 경우, 두 개의 제약 조건을 가진 배낭은 강한 NP-hard가 아니며, 최적 목표가 다항식으로 [4]경계가 되어도 FPTAS가 없다.

일부 강한 NP-완전 문제는 여전히 평균적으로 해결하기가 쉬울 수 있지만 실제로 어려운 사례가 발생할 가능성이 높습니다.

강력하고 약한 NP-경도 대 강하고 약한 다항식 시간 알고리즘

P != NP라고 가정하면 [5]정수의 계산 문제에 대해 다음과 같은 문제가 발생합니다.

  • 문제가 약하게 NP-hard일 경우 약하게 다항식 시간 알고리즘(정수의 수와 최대 정수의 비트 수에서 다항식)이 없지만 의사다항식 시간 알고리즘(정수의 수와 최대 정수의 크기에서 다항식)이 있을 수 있습니다.예를 들어 파티션의 문제가 있습니다.약한 NP 경도와 약한 다항식 시간은 모두 이진 부호화의 입력 에이전트 인코딩에 해당합니다.
  • 문제가 강한 NP-hard일 경우 의사 다항 시간 알고리즘도 없습니다.또한 완전 다항 시간 근사 체계를 가지고 있지 않다.예를 들어, 3 파티션의 문제가 있습니다.강한 NP 경도와 의사 다항 시간은 모두 입력 에이전트를 단항 부호화하는 것에 대응한다.

레퍼런스

  1. ^ Garey, M. R.; Johnson, D. S. (July 1978). "'Strong' NP-Completeness Results: Motivation, Examples, and Implications". Journal of the Association for Computing Machinery. New York, NY: ACM. 25 (3): 499–508. doi:10.1145/322077.322090. ISSN 0004-5411. MR 0478747.
  2. ^ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8. MR 1851303.
  3. ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.
  4. ^ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer.{{cite book}}: CS1 maint: 작성자 파라미터 사용(링크)
  5. ^ Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".