NP등가

계산 복잡성 이론에서 복잡성 등급 NP 등가치는 NP-편리성과 NP-하드 둘 다인 함수 문제의 집합이다.^[1]NP 등가치는 기능 문제에 대한 NP-완전성의 아날로그다.

예를 들어 FIND-SUBset-SUM 문제는 NP-등가성에 있다.정수의 집합이 주어진 경우, FIND-SUBset-SUM은 0까지 더하는 정수의 일부 비어 있지 않은 부분 집합을 찾는 문제(또는 그러한 부분 집합이 없는 경우 빈 세트를 반환하는 문제)이다.이 최적화 문제는 의사결정 문제 SUEMP-SUM과 유사하다. 정수의 집합으로 볼 때, SUEMP-SUM은 0에 대한 부분집합이 존재하는지 여부를 찾는 문제다.SUMET-SUM은 NP-완전하다.

FIND-SUBset-SUM이 NP와 동등하다는 것을 보여주기 위해서는 NP-hard와 NP-sossible임을 보여줘야 한다.

분명히 그것은 NP-hard이다.단위 시간에 FIND-SUBset-SUM을 해결한 블랙박스가 있다면 SUMSUM을 쉽게 해결할 수 있을 것이다. 블랙박스에 합계가 0인 서브셋을 찾도록 요청하면 비어있지 않은 세트를 반환했는지 여부를 확인하십시오.

그것은 또한 NP-편리하다.SUPT-SUM을 단위 시간에 풀 수 있는 블랙박스가 있다면 FIND-SUBset-SUM을 풀 수 있을 것이다.만약 그것이 거짓으로 돌아온다면, 우리는 즉시 빈 세트를 돌려준다.그렇지 않으면, 우리는 각 요소를 순서대로 방문하여 SUPSUM을 제거한 후에도 여전히 참으로 되돌아온다는 전제하에 제거한다.일단 우리가 모든 원소를 방문하고 나면, 우리는 더 이상 어떤 원소도 진실에서 거짓으로 바꾸지 않고는 제거할 수 없을 것이다; 이 시점에서 원래의 원소의 나머지 부분집합은 0이 되어야 한다.이것은 우리가 나중에 요소들을 제거한다고 해서 이전 요소들의 제거가 정답이 진실에서 거짓으로 바뀌었다는 사실이 바뀌지 않는다는 것을 알아둘 것을 요구한다.유사 코드:

FIND-Subset-SUM(set S)이 아닐 경우(SUBSET-SUM(S)이 S의 각 x에 대해 {}을(를) 반환하는 경우 := S – {x}

NP와 동등한 문제로 잘 알려진 또 다른 문제는 여행 판매원 문제다.

메모들

참조

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.