다루기 쉬운 Krom 공식의 동등성?

Question

내가 두 개를 가지고 있다고 가정하자 크롬 공식 $\psi_1, \psi_2$.Krom 공식은 모든 절에 2개의 리터럴이 있는 CNF의 명제 공식입니다.각 리터럴은 부정되거나 부정 해제될 수 있습니다.다시 말해서, $\psi_1,\psi_2$ 2-CNF 공식입니다.예를 들어:

$(x_1 \vee eg x_2) \land ( eg x_2 \vee x_3 ) \land (x_3 \vee x_4)$

여부를 결정하고 싶습니다. $\psi_1,\psi_2$ 논리적으로 동일합니다. 즉, $\psi_1 \leftrightarrow \psi_2$.마찬가지로, 나는 $F=(\psi_1 \vee eg\psi_2)\웨지( eg \psi_1 \vee \psi_2)$ 의 모든 과제에 해당됩니다. $x_1,\점,x_n$.

이 문제는 다루기 쉬운가요?

Answer 1

예, 등가는 다항식 시간 (실제로 2 차 시간)에서 확인할 수 있습니다.

$ \ psi_1 \ lor \nneg \ psi_2 $ 이 모든 과제에 해당하는지 여부를 테스트하는 방법을 설명합니다. $ \ psi_2 $ \ lor>에 대해서도 동일하게 수행하고 $ f $ 은 $ \ psi_1, \ psi_2 $ 이 논리적으로 동등한 것입니다.

$ \ psi_1 \ lor \nneg \ psi_2 $ 이 할당에 대해 false이거나 $ \ neg (\ psi_1 \ lor \ neg \ psi_2) $ 은 만족할 만합니다.

에 주목하십시오

$$ \ Neg (\ psi_1 \ lor \ Neg \ psi_2)=Neg \ psi_1 \ land \ psi_2, $$

$ \ psi_2 $ \ span> 여기서 $ \ psi_1, \ PSI_2 $ 은 KROM (2-CNF) 수식입니다.

$ \ psi_1= c_1 \ land \ cdots \ land c_k $ 여기서 $ c_i $ $ \ psi_1 $ 의 $ i $ th 절입니다. 그런 다음

$$ \ NEG \ PSI_1= (\ NEG C_1) \ LOR \ CDOTS \ lor (\ NEG C_K). $$

따라서

$$ \ begin {Align *} \ Neg \ PSI_1 \ Land \ PSI_2 &= (\ NEG C_1) \ lor \ cdots \ lor (\ Neg C_K)) \ Land \ PSI_2 \\ &= (\ NEG C_1 \ LARD \ PSI_2) \ LOR \ CDOTS \ lor (\ NEG C_K \ LARD \ PSI_2). \ end {정렬 *} $$

이제 $ \ neg \ psi_1 \ land \ psi_2 $ 은 만족도 IFF $ \ neg c_i \ land \ psi_2 $ 은 일부 $ i $ 에 만족할 만합니다. 따라서 우리는 $ i $ 을 반복하고 각 $ \ neg C_I \ LARD \ psi_2 $ ; 그 중 누구라도 만족할 수있는 경우 $ \ psi_2 $ \ lor \ psi_2 $ 은 만족스럽고 $ f $ 은 해양학이 아니며 $ \ psi_1, \ psi_2 $ 은 논리적으로 동등하지 않습니다.

$ \ neg C_I \ Land \ PSI_2 $ 의 만족성을 테스트하는 방법? 음, $ C_I $ 은 $ (\ el_1 \ lor \ el_2) $ $ \ ell_1, \ ell_2 $ 은 두 개의 리터럴이므로 $ \ neg C_I \ LARD \ PSI_2 $ 은 양식을 가지고 있습니다 < SPAN 클래스="수학 - 컨테이너"> $ \ NEG \ ELL_1 \ LARD \ NEG \ ELL_2 \ LARD \ PSI_2 $ . 이것은 또한 KROM (2-CNF) 공식이므로 표준 다항식 알고리즘을 사용하여 만족 성을 테스트 할 수 있습니다. 이러한 테스트의 선형 수를 수행하므로 총 실행 시간은 다항식입니다. 사실, 선형 시간으로 테스트 만족 가능성이 수행 될 수 있으므로 이차적입니다.

Answer 2

강하게 연결된 구성요소를 사용하는 2-SAT 솔루션을 떠올려보세요.꼭짓점으로 그래프를 만듭니다. $x_1,\ldots,x_n, \lnot x_1, \ldots, \lnot x_n$, 각 절을 교체합니다. $x_i \lor x_j$ 가장자리가 있는 $\lnot x_i o x_j$ 그리고 $\lnot x_j o x_i$.의 예 여기:

공식을 만족하려면 그래프에 모순이 없도록 꼭짓점을 할당하는 것이 필요하고 충분합니다. $true o false$).우리는 동등성 검사를 위해 이 그래프를 사용할 것입니다.

1. 우리는 이러한 그래프를 작성합니다 $G_1$ 그리고 $G_2$ 두 수식 모두에 대해 $F_1$ 그리고 $F_2$.
2. 주기가 있는 경우 $x_i \leadsto \lnot x_i \leadsto x_i$ 그래프에서는 공식에 해가 없습니다.두 공식 모두 풀 수 있는지/풀 수 없는지 확인합니다.
3. 형태의 길이 있다면 $x_i \leadsto \lnot x_i$ (이 경우도 마찬가지 $\lnot x_i \leadsto x_i$), 우리는 공식을 만족시키기 위해 선택해야 한다는 것을 알고 있습니다. $x_i$ 거짓이다(그렇지 않으면 모순이 된다).우리는 이 선택을 기억합니다.그래프를 사용하여 다음에서 도달할 수 있는 모든 정점에 값을 할당할 수 있습니다. $\lx_i$가 아님 (그들은 사실이어야 합니다).다시 한번 두 공식이 결국 정확히 동일한 결정을 내렸는지 확인하세요.
4. 그래프에서 알려진 모든 꼭지점과의 모든 모서리를 제거합니다.
5. 지금, $F_1$ 그리고 $F_2$ 동등하다 $\iff$ 나머지 그래프는 다음과 같은 의미에서 동일합니다.어떠한 것도 $v_1,v_2$ 길 $v_1 \leadsto v_2$ 에 존재 $G_1$ 만약 그것이 존재한다면 $G_2$.최대 체크인 가능 $O(|V|\cdot|E|)$ 시간(각 정점에서 DFS를 실행하고 두 그래프에 대해 동일한 정점을 방문했는지 확인하세요).어쩌면 더 빨리 완료될 수도 있습니다.

증거:

$\왼쪽 화살표$:그래프를 전이적으로 닫은 후에는 두 공식 모두에서 동일한 의미를 갖기 때문에 분명합니다.

$\오른쪽화살표$:모순으로.Wlog에서는 경로가 존재한다고 가정합니다. $v_1 \leadsto v_2$ ~에 $G_1$ 에는 존재하지 않는 것 $G_2$.그 임무를 의미한다 $v_1 := 참$, $v_2 := 거짓$ 에서 가능하다 $F_2$ (길이 없기 때문에 $v_1 \leadsto v_2$) 그러나 다음에서는 실행 불가능하다 $F_1$.

즉, 다음 과제는 $F_2$:

• $사실$ 도달할 수 있는 모든 정점에 대해 $v_1$.
• $false$ 도달할 수 있는 모든 정점으로부터 $v_2$.
• 그래프에서 알려진 모든 정점(위에서 언급한 정점과 해당 보완 정점)을 제거합니다.나머지 모든 정점은 연결된 구성요소를 생성합니다.연결된 구성 요소에 색상을 지정합니다. $사실$, 그리고 그 보완물에 해당하는 연결된 구성 요소 - $false$ (아래 참고 참조).

이 할당에는 우위가 있을 수 없으므로 모순이 없습니다. $u o v$ 형태의 $true o false$:

• 만약에 $u$ 풀컬러된 구성요소에 속합니다. $사실$, 그럼 그런 $v$ 또한 사실이어야 합니다.
• 그렇지 않으면 다음을 의미합니다. $u$ 에서 연결할 수 있습니다 $v_1$, 따라서 $v$ 다음에서도 연결할 수 있습니다. $v_1$ 그리고 사실이어야 합니다. $\블랙스퀘어$

기술 노트:각 변수에 대해 $x_i$ 두 개의 정점이 있습니다: $v_i$ 그리고 $\lnot v_i$ - 그리고 그것이 과제에 문제를 일으킬지 궁금할 수도 있습니다.대답은 4) 단계 이후에, $v_i$ 그리고 $\lnot v_i$ 두 개의 서로 다른 구성 요소에 있습니다(또한 대칭적입니다. $u o v$ 하나의 구성 요소에서 의미 $\lnot u o \lnot v$ 다른 것에서는).그러므로 우리가 어떤 결정을 내리든 $u$ 한 구성 요소에서는 반대 결정을 내릴 수 있습니다. $\l너는 $\l아님 또 다른 것.