문제가 NP 완전하다는 것을 증명하는 방법은 무엇입니까?

문제가 NP 완전하다는 것을 증명하는 방법은 무엇입니까?

---

일정에 문제가 있습니다. 문제가 NP 완전하다는 것을 증명해야합니다. NP 완료를 증명하는 방법은 무엇입니까?

---

문제가 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에서도).

---

NP-Complete 문제를 현재 가지고있는 문제로 줄여야합니다. 다항식 시간 내에 감소를 수행 할 수 있다면 문제가 이미 NP에있는 경우 문제가 NP 완전하다는 것을 증명 한 것입니다.

NP- 완전 문제보다 쉽지는 않습니다. 다항식 시간에 문제를 NP-Hard로 만들 수 있기 때문입니다.

자세한 내용은 http://www.ics.uci.edu/~eppstein/161/960312.html 의 끝을 참조하십시오 .

---

첫째, 당신은 그것이 NP에 있다는 것을 보여줍니다.

그런 다음 이미 알고있는 또 다른 문제가 NP 완료라는 것을 발견하고 문제에 대한 NP 어려움 문제를 다 항적으로 줄이는 방법을 보여줍니다.

---

문제 L이 NP 완전하다는 것을 증명하려면 다음 단계를 수행해야합니다.

1. 문제 L이 NP에 속한다는 것을 증명하십시오 (즉, 솔루션이 주어지면 다항식 시간에 확인할 수 있음).
2. 알려진 NP- 완전 문제 선택 L '
3. L '을 L로 변환하는 알고리즘 f를 설명하십시오.
4. 알고리즘이 정확함을 증명하십시오 (공식 : x ∈ L 'if 및 if and only if f (x) ∈ L)
5. algo f가 다항식 시간에 실행된다는 것을 증명

---

1. NP Complete 문제의 하위 집합에 익숙해지기
2. NP 경도 증명 : NP 완전 문제의 임의의 인스턴스를 문제의 인스턴스로 줄입니다. 이것은 파이의 가장 큰 조각이며 NP Complete 문제에 대한 친숙 함이 지불하는 곳입니다. 선택한 NP Complete 문제에 따라 감소가 다소 어려울 것입니다.
3. 문제가 NP에 있음을 증명하십시오 : 인스턴스가 솔루션인지 다항식 시간에 확인할 수있는 알고리즘을 설계하십시오.

참고 URL : https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete