algorithm

문제가 NP 완료임을 표시하려면 다음을 수행해야합니다.

NP로 표시

즉, 일부 정보가 주어지면 도메인에 있는지 여부에 관계없이 가능한 모든 입력을 확인 C하는 다항식 시간 알고리즘 V을 만들 수 있습니다 .XX

예

정점 커버 의 문제 (즉, 일부 그래프의 G경우 모든 가장자리 가 커버 세트에 적어도 하나의 정점이있는 크기의 정점 커버 세트가kG 있습니까?)가 NP에 있음을 증명 하십시오 .

• 입력 X은 그래프 G와 숫자입니다 k(문제 정의에서 가져온 것입니다)

• 우리의 정보를 가지고 C“그래프의 정점의 가능한 모든 부분 집합으로 G크기 k“

• 그런 다음 우리는 알고리즘을 쓸 수 V주어진 G, k그리고 C정점의 집합에 대한 정점 커버 있는지 여부를 반환합니다, G에, 또는하지 다항식 시간 .

그런 다음 모든 그래프 G에 대해 정점 커버 인 ” G크기 의 정점의 가능한 하위 집합 k“이 G있으면에 NP있습니다.

주 우리가 할 것을 하지 찾을 필요가 C다항식 시간에. 가능하다면 문제는`P.

참고 알고리즘이 것을 V위해 일해야 모든 G 일부, C. 모든 입력에 대해 입력이 문제 도메인에 있는지 여부를 확인하는 데 도움 이되는 정보 가 있어야 합니다 . 즉, 정보가 존재하지 않는 곳에 입력이 없어야합니다.

NP Hard 증명

여기에는 다음과 같은 형식의 부울 식 집합 인 SAT 와 같은 알려진 NP- 완전 문제 가 포함됩니다.

(A 또는 B 또는 C) 및 (D 또는 E 또는 F) 및 …

식이 만족 스러우면 이러한 부울에 대한 일부 설정이 있으므로식이 true가 됩니다.

그런 다음 다항식 시간에서 NP- 완전 문제를 문제로 줄 입니다.

즉, (또는 사용중인 NP- 완전 문제에 X대한) 입력이 주어지면 SAT문제에 Y대한 입력 을 생성 합니다. 문제 X가있는 경우에만 SAT Y에 있습니다. 함수 f : X -> Y는 다항식 시간에 실행되어야합니다 .

위의 예에서 입력 Y은 그래프 G와 꼭지점 덮개의 크기입니다 k.

완전한 증거 를 얻으 려면 다음 두 가지를 모두 증명해야합니다.

• 그것은 X이다 SAT> = Y문제에

• 그리고 Y문제의 => X에서 SAT.

marcog의 답변에는 문제로 줄일 수있는 몇 가지 다른 NP- 완전 문제와 연결되어 있습니다.

각주 : 2 단계 ( NP-hard임을 증명 )에서 다른 NP-hard (반드시 NP-complete는 아님) 문제를 현재 문제로 줄이면 NP- 완전 문제는 NP-hard 문제 (즉, NP에서도).

---

답변