정확히 3개의 개별 변수가 있는 Monotone 3-SAT는 다루기 어렵습니까?

Question

나는 다음과 같은 SAT 변형을 제공했습니다.

각 절 C에 정확히 3개의 개별 리터럴이 있고 F의 각 C에 대해 모든 리터럴이 양수이거나 모든 리터럴이 부정되는 CNF의 수식 F가 제공됩니다.예:

$F= (x_1\vee x_2 \vee x_4) \쐐기 ( eg x_2\vee eg x_3 \vee eg x_4) \쐐기 (x_3\vee x_4 \vee x_5)$

SAT의 변형이 다루기 쉬운가요?

지금까지 내 결과는 다음과 같습니다.

나는 문제가 NP-완전한 문제이므로 다루기 힘든 것으로 생각합니다.따라서 나는 3-SAT에서 위에서 설명한 변형으로 다중 축소를 수행하고 싶습니다.

임의의 3-SAT 수식을 단조로운 3-SAT로 변환할 수 있습니다.

다음 예를 들어보세요:

$C_1=(x_1\vee x_2 \vee eg x_3)$ 정의하고 $z_3$ ~에 의해 $ eg x_3 \leftrightarrow z_3$ 그리고 $x_3 \leftrightarrow eg z_3$ 이는 다음과 같습니다. $(x_3\vee z_3)\쐐기( eg x_3 \vee eg z_3)$.

그것으로부터 우리는 단조로운 형태를 얻습니다. $C_1$ ~에 의해

$(x_1\vee x_2 \vee eg x_3) \leftrightarrow (x_1\vee x_2 \vee z_3)\wedge (x_3\vee z_3)\wedge( eg x_3 \vee eg z_3)$

이 변환을 모든 절에 적용함으로써 동일하게 만족스러운 단조로운 3-SAT 공식을 얻습니다.

내 축소에서는 모노톤이 아닌 각 절에 대해 2개의 리터럴이 있는 추가 2개의 절이 생성됩니다. 그런데 정확히 3개의 개별 리터럴이 있는 단조로운 절만 얻으려면 어떻게 해야 합니까?

Answer 1

나는 이제 내 자신의 질문에 대답하려고 노력할 것이며 정확성에 관한 피드백에 대해 기쁘게 생각합니다.

Kyle Jones가 논의하고 지적한 위의 질문과 마찬가지로 임의의 3-SAT 공식을 단조로운 3-SAT 공식으로 줄일 수 있습니다.

예를 들어 조항 $C=(x_1\vee x_2 \vee eg x_3)$ 로 변환될 수 있다 $C'(x_1\vee x_2 \vee z_3)\쐐기(z_3 \vee x_3) \쐐기( eg z_3 \vee eg x_3)$.다음과 같은 경우 확인할 수 있습니다. $C$ 만족스럽다 $C'$ 이것도 만족스럽고 그렇다면 $C$ 만족스럽지 않다 $C'$ 역시 만족스럽지 않습니다.

다음 단계는 3개 미만의 리터럴이 있는 모든 절을 정확히 3개의 개별 리터럴이 있는 절로 변환하는 것입니다.

그러므로 예를 들어보자 $C_1=(x_1 \vee x_2)$ 그리고 그것을로 변환 $C_1'=(x_1 \vee x_2 \vee y_1)\쐐기(x_1 \vee x_2 \vee y_2) \쐐기(x_1 \vee x_2 \vee y_3) \쐐기( eg y_1 \vee eg y_2 \vee eg y_3)$ 그럼 또 만약에 $C_1$ 만족스럽다 $C_1'$ 이것도 만족스럽고 그렇다면 $C_1$ 만족스럽지 않다 $C_1'$ 역시 만족스럽지 않습니다.부정적인 경우에도 동일한 작업을 수행할 수 있습니다. $C_2=( eg x_1 \vee eg x_2)$ 로 변형될 수 있다 $C_2'=( eg x_1 \vee eg x_2 \vee eg u_1)\쐐기( eg x_1 \vee eg x_2 \vee eg u_2) \쐐기( eg x_1 \vee eg x_2 \vee \ 음 u_3) \웨지 ( u_1 \vee u_2 \vee u_3)$

두 가지 변환을 적용하면 임의의 3-SAT 인스턴스를 정확히 3개의 고유 리터럴이 있는 단조로운 3-SAT 인스턴스로 변환할 수 있습니다.위에서 쉽게 볼 수 있듯이 변환에는 다항식 복잡성이 있습니다.따라서 3-SAT는 NP-하드이므로 감소도 NP-하드여야 합니다.