의 NP-완전성 = {A 1하는 2 ...하는 N} 명명 B의증명 우리는 세트 A에 주어진 문제
주어 서브셋 1 , B , ..., m. H라는 A의 부분 집합이 주어진 B의 모든 부분과 교차하는 경우 H를 "Covering subset"이라고 부릅니다. 주어진 A와 B에 대해 크기 K의 "커버 하위 집합"(H의 카디널리티가 K)이 있습니까? 이 문제가 NP-Complete임을 입증하십시오.
일부 알려진 문제를 "부분 집합을 덮는"문제로 줄여야합니다.
업데이트 이것을 hitting set이라고합니다. 위키 백과에서 같은 대답을 읽을 수 있습니다.
이 문제는 어떤면에서는 set cover problem과 중복됩니다.
일부 용어가 변경됩니다. {B1, B2, ...}을 요소로하고 {a1, a2, ...}을 세트로 둡니다. '설정'Bj에 원래 문제가있는 ai이 있으면 Bj에 'element'요소가 포함되어 있습니다.
이제 모든 '요소'를 포함하는 '세트'ai의 최소 개수를 선택하면됩니다. Bj. 그리고 그 문제는 위의 링크에서 볼 수 있듯이 NP 완성입니다.
변환을 명확히하기 위해 set/element를 바꾸고 contains/contains를 사용하여 하나의 문제 정의를 생성 할 수 있습니다.
마다 다음과 같은 비교는 Bj가 ai이
모든 '요소'Bj 일부 선택 ai
스택 오버플로가 숙제 도움의 사이트가 아닙니다 '설정'에 포함되는 몇 가지 선택 요소가 포함 설정합니다. 질문을 수정하고 혼동스러워하는 점을 설명하십시오. – Yuliy
이것은 어쨌든 programmers.stackexchange.com에 속합니다. – chx
@Yuliy : 실제로, 여러 번 있습니다. 그리고 거기에는 아무런 문제가 없습니다. 물론 OP는 해결책을 찾는데 아무런 노력을 기울이지 않았기 때문에 그를 돕는 사람을 볼 수 없습니다. –