NP-경도

NP-hardness
보다 온화한 도입에 대해서는, 「P 대 NP 의 문제」를 참조해 주세요.
Euler diagram for P, NP, NP-complete, and NP-hard set of problems.
P, NP, NP-완전 및 NP-하드 문제에 대한 오일러 다이어그램입니다.왼쪽은 PnpNP라고 가정할 때 유효하며 오른쪽은 P=NP라고 가정할 때 유효하다(빈 언어와 그 보완어는 NP-완전하지 않음).

계산 복잡도 이론에서, NP-난이도(비결정론적 다항식-시간 경도)는 비공식적으로 "적어도 NP에서 가장 어려운 문제만큼 어려운" 문제의 종류를 정의하는 특성이다.NP-하드 문제의 간단한 예로는 서브셋합 문제가 있습니다.

보다 정확한 사양은 NP의 모든 문제 L이 다항 시간에서 H로 감소될 수 있을 때 문제 H는 NP-hard이다. 즉, H에 대한 해법이 1단위 시간이 걸린다고 가정하면 H의 해법을 사용하여 다항 시간 내에 [1][2]L을 해결할 수 있다.결과적으로, NP-하드 문제를 해결하기 위한 다항 시간 알고리즘을 찾는 것은 NP의 모든 문제에 대한 다항 시간 알고리즘을 제공할 것이다.PµNP가 의심되므로 이러한 알고리즘이 [3]존재할 가능성은 거의 없습니다.

NP-hard 문제에 대한 다항 시간 알고리즘은 없는 것으로 의심되지만, 그것은 [4]증명되지 않았습니다.게다가 모든 문제를 다항 시간에 풀 수 있는 클래스 P는 NP [5]클래스에 포함된다.

정의.

판정 문제 H는 NP의 모든 문제 L에 대해 L에서 [1]: 80 H로 다항식 시간 다원 감소가 있을 때 NP-hard이다.동등한 정의는 NP의 모든 문제 L을 [6]H에 대한 오라클을 가진 오라클 머신에 의해 다항식 시간 내에 해결할 수 있도록 요구하는 것입니다.비공식적으로 이러한 오라클 머신을 H를 풀기 위한 서브루틴으로 호출하고 서브루틴 호출이 계산하는데 한 단계만 걸리면 다항식 시간 내에 L을 해결하는 알고리즘을 생각할 수 있다.

또 다른 정의는 NP-완전 문제 G에서 [1]: 91 H로 다항 시간 감소를 요구하는 것입니다. NP의 문제 L이 다항 시간 G에서 G로 감소함에 따라 L은 다항 시간에서 H로 감소하므로 이 새로운 정의는 이전 정의를 암시합니다.이상하게도 클래스 NP-hard는 결정 문제로 제한되지 않으며 검색 문제 또는 최적화 문제도 포함됩니다.

결과들

만약 P , NP라면, NP-난이도 문제는 다항식 시간에 풀 수 없다.

일부 NP-하드 최적화 문제는 일정한 근사 비율(특히 APX에 있는 문제) 또는 임의의 근사 비율(PTAS 또는 FPTAS에 있는 문제)까지 다항 시간 근사할 수 있습니다.

예

NP-hard 문제의 예로는 결정 서브셋의 합계 문제가 있습니다.정수의 집합이 주어졌을 때, 그 중 비어 있지 않은 서브셋이 모두 0이 됩니까?그것은 결정상의 문제이며, 공교롭게도 NP완료입니다.NP-hard 문제의 다른 예로는 가중 그래프의 모든 노드를 통해 최소비용의 사이클 루트를 찾는 최적화 문제가 있습니다.이것은 일반적으로 출장 세일즈맨 [7]문제로 알려져 있습니다.

정지 문제 등 NP-hard이지만 NP-complete가 아닌 결정 문제가 있습니다.그것이 "프로그램과 그 입력이 주어지면 영원히 실행될 것인가?"라는 질문이다.그것은 예/아니오 질문이고 결정 문제도 마찬가지입니다.정지 문제가 NP-hard이지만 NP-complete가 아님을 쉽게 증명할 수 있습니다.예를 들어, 부울 만족도 문제는 모든 진실값 할당을 시도하고 공식을 만족시키는 튜링 기계의 설명으로 변환함으로써 정지 문제로 축소될 수 있으며, 그렇지 않으면 무한 루프가 된다.또한 NP의 모든 문제는 한정된 수의 연산으로 결정 가능하지만 일반적으로 정지 문제는 결정 불가능하기 때문에 정지 문제가 NP에 없다는 것을 쉽게 알 수 있습니다.또한 NP-완전하지도 않고 결정하지도 않는 NP-하드 문제도 있습니다.예를 들어, 진정한 양자화된 부울 공식의 언어는 다항식 공간에서는 결정 가능하지만, 비-다항식 시간에서는 결정 가능하지 않다(NP [8]= PSPACE가 아닌 경우).

NP 명명 규칙

NP-하드 문제는 복잡도 클래스 NP의 요소일 필요는 없습니다.NP는 계산 복잡도에서 중심적인 역할을 하기 때문에 다음과 같은 여러 클래스의 기초로 사용됩니다.

NP
결정론적 튜링 기계(또는 비결정론적 튜링 기계로 다항식 시간에 해결 가능)에 의해 주어진 예스 해법이 다항식 시간에서의 해결책으로 검증될 수 있는 계산 결정 문제의 클래스.
NP 하드
적어도 NP에서 가장 어려운 문제만큼 어려운 문제의 종류. NP-난해한 문제는 NP의 요소가 될 필요가 없습니다.실제로 그것들은 결정조차 할 수 없습니다.
NP-완전
NP에서 가장 어려운 문제를 포함하는 결정 문제의 클래스. 각 NP-완전 문제는 NP여야 합니다.
NP-쉽다
NP만큼 어렵지만 반드시 NP일 필요는 없습니다.
NP 등가
NP 하드와 NP 모두 쉽지만 반드시 NP일 필요는 없는 의사결정 문제.
NP-중간
P와 NP가 다르면 NP 영역에는 P와 NP-완전 문제 사이에 있는 결정 문제가 존재합니다.(P와 NP가 같은 클래스일 경우 NP-완전 문제는 모두 P에 속하기 때문에 NP-중간 문제는 존재하지 않으며, 정의상 NP의 모든 문제는 NP-완전 문제로 축소될 수 있습니다.m.)

응용 프로그램 영역

NP-hard 문제는 다음과 같은 영역에서 규칙 기반 언어로 처리되는 경우가 많습니다.

레퍼런스

  1. ^ a b c Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.
  2. ^ Knuth, Donald (1974). "Postscript about NP-hard problems". ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. S2CID 46480926.
  3. ^ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0-13-915380-2.
  4. ^ "Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP". www.scottaaronson.com. Retrieved 2016-09-25.
  5. ^ "PHYS771 Lecture 6: P, NP, and Friends". www.scottaaronson.com. Retrieved 2016-09-25.
  6. ^ V. J. Rayward-Smith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0-632-01307-9.
  7. ^ 를 클릭합니다Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9.
  8. ^ 보다 정확하게는 이 언어는 PSPACE-complete입니다.예를 들어, 을 참조해 주세요.