vzn의 주석을 답으로 확장 : CNF-SAT에서 정점 표지로의 표준 축소는 매우 쉽습니다. 각 항 (변수 또는 부정)에 대한 정점을 만들고, 각 변수를 모서리에 의해 부정에 연결하고, 각 절을 클릭하십시오. 절의 각 정점을 절의 용어 중 하나에 대한 정점에 연결합니다. 알려진 만족스러운 할당으로 만족도 문제로 시작하면 알려진 최적의 솔루션으로 정점 커버 문제가 발생합니다 (할당으로 주어진 정점이라는 용어를 선택하고 각 절에서 하나의 정점을 제외한 모든 정점을 선택하십시오. 선택되지 않은 절 정점은 선택되는 정점에 인접합니다).

따라서 이제 만족스러운 할당이 있지만 솔루션을 찾기 어려운 만족도 문제를 찾아야합니다. 하드 만족도 문제를 생성하는 알려진 방법이 많이 있지만 (예 : 만족도 임계 값에 가까운 임의의 k-SAT 인스턴스 생성) 만족스러운 할당을 알고 있다는 추가 요구 사항은 가능성을 제한합니다. 여기서 할 수있는 한 가지는 분해와 같은 암호화 적으로 어려운 문제에서 다른 수준의 축소를 거치는 것입니다. 즉, 두 개의 큰 소수 p와 q를 선택하고 p와 q를 이진수로 곱하기위한 부울 회로를 설정 한 다음 각 입력 (p와 q) 및 각 중간 값에 대한 변수가있는 CNF 공식으로 변환합니다. 회로의 와이어, 각 출력에 올바른 값을 갖도록 강제하는 조항, 및 게이트의 입력 및 출력이 서로 일치하도록하는 각 게이트에 대한 조항. 그런 다음이 CNF 공식을 정점 표지로 변환하십시오.

보다 간단한 전략을 위해서는 먼저 3CNF 수식에 만족할만한 할당을 선택한 다음 할당과 일치하는 절만 유지하면서 절을 임의로 생성 한 다음 정점 표지로 변환하십시오. 절이 균일 한 확률을 갖는 경우 이는 학위 기반 휴리스틱에 취약 할 것입니다 (선택된 할당과 일치하는 정점이라는 용어는 그렇지 않은 정점보다 낮은 등급을 갖습니다). 그러나 이러한 단점은 절의 확률을 조정하여 피할 수 있습니다 선택한 조항에 동의하는 조항의 조항 수에 따라 아마도 이것은 일종의 다항식 시간 공격에 취약하지만 정점 커버에는 자연스럽지 않을 수 있으므로 경도를 많이 보장하지 않아도 좋은 테스트 인스턴스를 만들 수 있습니다.

답변