2 성분 문제에서 구현 문제

Question

10 만 리터 스 문제에 대해 2-SAT 문제를 구현하고 싶습니다. 따라서 200000 개의 정점이있을 것입니다. 그래서 나는 각 정점에서 모든 접근 가능한 정점 배열을 가지고 있는데, 공간 복잡성 O(200000^2) 불가능하므로 이에 대한 해결책을 제안하십시오. 그리고 2-SAT 문제의 효율적인 구현에 대해 약간의 빛을 발하십시오.

Answer 1

에서 위키 백과:

... 다항식 시간에 2- 자만성을 해결할 수 있습니다. 처럼 Aspvall, Plass & Tarjan (1979) 관찰 된 경우, 인스턴스의 모든 변수가 동일한 변수의 부정과 관련하여 암시 적 그래프의 다른 강하게 연결된 구성 요소에 속하는 경우에만 2- 자만적 인 인스턴스가 해결 될 수 있습니다. 강하게 연결된 구성 요소는 깊이 첫 번째 검색에 기초한 알고리즘에 의해 선형 시간에 발견 될 수 있으므로, 동일한 선형 시간 경계가 2- 성분에도 적용됩니다.

나는 그 단락의 대부분을 이해하는 척하지는 않지만 거기에서 보일 것입니다. ~이다 2-SAT 문제를 해결하는 데 사용할 수있는 알고리즘은 참조 된 문서 내에 설명됩니다 (특정 정량화 된 부울 공식의 진실을 테스트하기위한 선형 시간 알고리즘). 약 $ 20 USD에 온라인으로 구입할 수 있습니다. 그것이 도움이 될지 확실하지 않지만 거기에 있습니다!

업데이트: 동일한 문서의 무료 PDF를 찾을 수 있습니다. 여기. 크레딧이 간다 liori 발견을 위해.

Answer 2

이 전체 스레드는 약간 엉망입니다. 예, 선형 시간에 2 -SAT를 해결할 수는 있지만 아니요. 많은 변수에 대해서는 해결할 수 없습니다. 2-SAT를 해결하는 시간은 의미의 수와 관련하여 선형입니다. . 다른 솔루션이 있습니다 (느리지 만 메모리가 많이 필요하지 않은 강력하게 연결된 구성 요소를 사용하지 않음).