약한 NP 완전성

Weak NP-completeness

계산 복잡도에서 NP-완전(또는 NP-hard) 문제는 실행 시간이 문제의 차원과 관련된 데이터의 크기(이것들이 정수로 주어질 경우)에 대한 알고리즘이 있는 경우 크기의 2진수 로그가 아닌 약 NP-완전(또는 약 NP-hard)입니다.이러한 알고리즘은 기술적으로 입력 크기의 지수 함수이므로 [1]다항식으로 간주되지 않습니다.

예를 들어, NP-하드 배낭 문제는 배낭의 크기와 항목 수에 다항식 단계를 필요로 하는 동적 프로그래밍 알고리즘으로 해결할 수 있습니다(모든 데이터가 정수로 스케일링된다고 가정함). 그러나 이 알고리즘의 실행 시간은 개체와 배낭의 입력 크기가 로그이기 때문에 지수 시간입니다.산술적 규모입니다.그러나 Garey와 Johnson(1979)이 관찰한 바와 같이, "의사 다항 시간 알고리즘은 우리가 관심 있는 애플리케이션에서는 드물게 "exponential behavior"를 포함하는 인스턴스에 직면했을 때만 "exponential behavior"를 표시합니다.그렇다면 이런 유형의 알고리즘은 다항식 시간 알고리즘과 마찬가지로 우리의 목적에 거의 부합할 수 있습니다."약한 NP-완전 문제의 또 다른 예는 부분집합 문제입니다.

관련 용어인 강한 NP-완전(또는 단항 NP-완전)은 데이터가 단항으로 인코딩되어도 NP-완전 상태로 유지되는 문제를 말합니다. 즉, 데이터가 [2]전체 입력 크기에 비해 "작은" 경우입니다.

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

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

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

레퍼런스

  1. ^ M. R. 개리와 D.S. 존슨컴퓨터와 난해성: NP-완전성 이론 가이드.1979년 뉴욕 주 W.H. 프리먼
  2. ^ L. 홀계산의 복잡성존스 홉킨스 대학이요
  3. ^ Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".