2개의 호환성

컴퓨터 과학에서 2-만족도, 2-SAT 또는 2-SAT는 변수 쌍에 대한 제약 시스템을 만족시키기 위해 각각 두 개의 가능한 값을 갖는 변수에 값을 할당하는 계산 문제이다.이것은 세 개 이상의 변수에 대한 제약 조건을 포함할 수 있는 일반적인 부울 만족도 문제와 각 변수의 값에 대해 세 개 이상의 선택을 허용하는 제약 만족도 문제의 특별한 경우입니다.그러나 NP-완전인 보다 일반적인 문제와는 달리 2-만족도는 다항식 시간으로 해결할 수 있습니다.

2-만족도 문제의 인스턴스는 일반적으로 연결 정규 형식(2-CNF) 또는 Krom 공식이라고 하는 특수한 유형의 부울 공식으로 표현됩니다.또는 특정 유형의 유도 그래프, 인스턴스의 변수와 그 부정을 그래프에서 꼭지점으로 표현하는 시사 그래프, 그리고 변수의 쌍에 대한 구속조건을 유도 에지로 표현할 수 있다.이러한 종류의 입력은 모두 역추적에 기초한 방법 또는 암시 그래프의 강하게 연결된 구성요소를 사용하여 선형 시간 내에 해결할 수 있다.분해능(resolution)은 구속조건 쌍을 결합하여 유효한 구속조건을 추가로 만드는 방법이며, 다항식 시간 해법으로 이어집니다.2-만족도 문제는 다항식 시간에 풀 수 있는 결합 정규 형식 공식의 두 가지 주요 하위 클래스 중 하나를 제공하고, 다른 하위 클래스 중 하나는 뿔-만족도이다.

2-동일성은 객체 집합이 각각 2개의 잠재적 위치를 가지며 다른 객체와의 중복을 회피하는 각 객체의 배치를 찾는 것이 목표인 기하학 및 시각화 문제에 적용할 수 있습니다.다른 애플리케이션에는 클러스터 지름의 합계를 최소화하기 위한 데이터 클러스터링, 강의실 및 스포츠 일정, 횡단면 정보에서 형상 복구 등이 있습니다.

계산 복잡도 이론에서 2-만족도는 NL-완전 문제의 예를 제시합니다.이 문제는 대수적 양의 스토리지를 사용하여 비결정적으로 해결할 수 있으며 이 리소스 바운드에서 해결할 수 있는 가장 어려운 문제 중 하나입니다.2-만족도 인스턴스(instance)에 대한 모든 솔루션 집합은 중위수 그래프의 구조를 제공할 수 있지만, 이러한 솔루션을 계산하는 것은 #P-완전이며, 따라서 다항식 시간 솔루션을 가질 것으로 예상되지 않습니다.랜덤 인스턴스는 변수에 대한 제약의 비율이 1을 초과하여 증가함에 따라 해결 가능한 인스턴스에서 해결 불가능한 인스턴스로 급격한 단계 전환을 겪는다. 이 현상은 더 복잡한 형태의 만족도 문제에 대해 추측되지만 입증되지 않은 현상이다.충족된 제약의 수를 최대화하는 진실 할당을 찾는 계산적으로 어려운 2-만족성의 변형은 최적성이 고유한 게임 추측에 따라 달라지는 근사 알고리즘을 가지며, 또 다른 어려운 변형은 진정한 변수의 수를 최소화하는 만족스러운 할당을 찾는 것이 중요하다.매개 변수화된 복잡성에 대한 est

문제의 표현

2-만족도 문제는 특별한 제한된 형식의 부울식을 사용하여 설명할 수 있습니다.이것은 절의 결합(부울과 연산)이며, 각 절은 2개의 변수 또는 부정 변수의 분리(부울 또는 연산)입니다.이 공식에 나타나는 변수 또는 부정을 ^[1]리터럴이라고 합니다.예를 들어, 다음 공식은 7개의 변수, 11개의 절 및 22개의 리터럴로 이루어진 결합 정규 형식입니다.

2-만족도 문제는 전체 공식을 참으로 만드는 변수들에 대한 진실 할당을 찾는 것입니다.이러한 할당은 각 변수를 true로 할지 false로 할지를 선택하기 때문에 모든 절에서 적어도1개의 리터럴이 true가 됩니다.위의 식에서는 7개의 변수를 모두 true로 설정하는 할당이 1개입니다.모든 구에는 하나 이상의 부정화되지 않은 변수가 있으므로 이 할당은 모든 구를 충족합니다.공식이 참이 되도록 모든 변수를 설정하는 다른 15가지 방법도 있습니다.따라서 이 식에 의해 나타나는 2-만족도 인스턴스는 만족할 수 있습니다.

이 형식의 수식은 2-CNF 수식으로 알려져 있습니다.이 이름의 "2"는 절당 리터럴 수를 나타내며 "CNF"는 연결 정규 형식을 나타냅니다. 연결 정규식은 ^[1]연결의 연결 형식 형식의 부울 표현식입니다.1967년 UC 데이비스 수학자 멜벤 R. 크롬의 논문이 2-만족도 ^[2]문제에 대한 최초의 연구 중 하나였기 때문에 크롬 공식이라고도 불립니다.

2-CNF 공식의 각 절은 논리적으로 하나의 변수 또는 부정 변수에서 다른 변수로의 의미와 동등합니다.예를 들어, 이 예의 두 번째 절은 다음과 같은 세 가지 방법으로 작성할 수 있습니다.

이러한 서로 다른 유형의 연산 간의 동등성 때문에 2-만족성 인스턴스는 함축적 정규 형식으로 작성될 수도 있습니다. 여기서 우리는 접속적 정규 형식의 각 또는 절을 동등한 ^[3]두 가지 함축적 정규 형식으로 대체합니다.

두 가지 만족도를 나타내는 세 번째 방법은 시사 그래프입니다.함축 그래프는 변수 또는 부정 변수당 하나의 정점이 있고 대응하는 변수가 인스턴스의 함축 정규 형태에서의 함축에 의해 관련될 때마다 하나의 정점과 다른 정점을 연결하는 엣지가 있는 유향 그래프입니다.암시 그래프는 각 변수를 음으로 변환하고 모든 ^[4]모서리의 방향을 반전시키는 대칭을 갖는 스큐 대칭 그래프여야 합니다.

알고리즘

2-만족도 문제를 해결하기 위해 몇 가지 알고리즘이 알려져 있습니다.그 중 가장 효율적인 것은 선형 ^[2][4][5]시간이 걸립니다.

해결 및 이행 종료

크롬(1967)은 2-만족도 ^[2]인스턴스 해결을 위한 다음과 같은 다항식 시간 결정 절차를 설명했다.

2-만족도 인스턴스(instance)에 동일한 변수 x를 사용하는 두 개의 절이 포함되지만 x는 한 절에서만 부정되고 다른 절에서는 부정된다고 가정합니다.그런 다음 두 절을 결합하여 두 절에 다른 두 리터럴이 포함된 세 번째 절을 생성할 수 있습니다. 이 세 번째 절도 처음 두 절이 모두 충족될 때마다 충족되어야 합니다.예를 들어${\displaystyle }$(${\displaystyle a}$${\displaystyle b}$b$$) \ $displaystyle$${\displaystyle }$($a$ \ $lor$ b$$) \$displaystyle$( \ $lnot$b \$llor$ \ $lnot$ c $)\$ displaystyle ( \ lor \ lnot c )를$$$$ 조합하여 (${\displaystyle ac}$c $)\$ $display$ style $( a$ \$lor$ \ $lnot$ c$)$를 Acn-f의 의미식으로 작성할 수 있습니다.$(\displaystyle\lnot$ a$\rightarrow$ b$)$ 및$$ $b{\displaystyle }$ $(\displaystyle$ b$\rightarrow\lnot$c$)$ 및 전송성에 의해 세 번째 의미를 추론합니다$displaystyle\lnot$ a$\rightarrow\lnot$ c$.$^[2]

Krom은 이 추론 규칙의 반복 적용으로 $변수{\displaystyle }$x${\displaystyle (\backslash }$$displaystyle$ $(x$${\displaystyle \backslash }$$lor$ x$))$와$lnot$x$lor \lnot$ x$)\displaystyle (\lor$ x$)\$lnot x$)\backslash$displaystyle (\lor x)\lnot x$)$의 두${\displaystyle }$절을 모두 생성할 수 없는 경우에만 공식이 일치한다고 기술합니다.nt. 수식이 일치하지 않으면 두 구$({\displaystyle x}$ ${\displaystyle x}$x $)(x\lor$ x$)$와${\displaystyle }$($lor x)$를 동시에$$ 만족시킬 수 없습니다.또한 일관성이 있는 경우 변수별로 일관성을 유지하면서 형식$({\displaystyle xx}$x $)(x\lor$ x$)$ 또는$$${\displaystyle }$(${\displaystyle x\mathrm{}}$x${\displaystyle }$x${\displaystyle x}$ x$$)(\$display$ style $(\lnot$x\$lor x))$의 구를 한 번에 1개씩 반복 추가함으로써 식을 확장할 수 있습니다.이러한 확장 단계 각각에서 일관성을 유지하면서 이 두 절 중 하나를 항상 추가할 수 있습니다. 그렇지 않으면 추론 규칙을 사용하여 다른 절을 생성할 수 있습니다.모든 변수에 이 형식의 절이 식에 포함되면 변수 $($${\displaystyle xx}$x $)$를 true로 설정하고 식에 구$({\displaystyle x\mathrm{\backslash }\mathrm{lor}}$$$x$)$가 $포함$된 경우 false로 설정함으로써 모든 변수를 만족스럽게 할당할 수 있습니다.laystyle $(\lnot$ x$\lor \lnot$ x$)\}$^[2] 입니다.

크롬은 알고리즘의 효율성보다는 추론 규칙 시스템의 완전성에 주로 관심이 있었다.그러나 그의 방법은 2-만족도 문제를 해결하기 위한 다항식 시간으로 이어진다.동일한 변수를 사용하는 모든 구를 그룹화하여 각 구 쌍에 추론 규칙을 적용함으로써 주어진 2-CNF 인스턴스에서 가능한 모든 추론을 찾을 수 있으며, 총 시간 O(n³)에서 일치하는지 여부를 테스트할 수 있습니다. 여기서 n은 인스턴스의 변수 수입니다.이 공식은 변수 수에 주어진 변수를 포함하는 절의 O(n²) 쌍 수를 곱하는 것으로, 추론 규칙이 적용될 수 있습니다.따라서 주어진 2-CNF 인스턴스가 시간 O(n³)에 적합한지 여부를 판단할 수 있습니다.Krom의 방법을 사용하여 만족스러운 과제를 찾는 것은 일련의 O(n) 일관성 검사를 수반하기 때문에 O(n⁴) 시간이 걸립니다.또, Itai & Shamir(1976)는, 이 알고리즘의 연산의 보다 신중한 순서에 근거해, 이 알고리즘의 O(n²)의 시간을 단축하고 있습니다.그럼에도 불구하고, 이 작은 시간 범위도 Even, Itai & Shamir(1976년)와 Aspvall, Plass & Tarjan(1979년)의 후기 선형 시간 알고리즘에 의해 크게 개선되었다.

2-만족도 인스턴스의 암시 그래프 측면에서, 크롬의 추론 규칙은 그래프의 전이적 닫힘을 구성하는 것으로 해석될 수 있다.쿡(1971)이 관찰한 바와 같이, 이는 데이비스의 사례로도 볼 수 있다.해상도 원리를 이용하여 만족도 문제를 해결하기 위한 풋남 알고리즘.그 정확성은 데이비스의 보다 일반적인 정확성에서 비롯된다.풋남 알고리즘이 다항식 시간 제한은 각 분해능 단계가 변수 ^[6]수의 2차 함수에 의해 상한 경계인 인스턴스의 절 수를 증가시킨다는 사실에서 비롯됩니다.

제한된 역추적

심지어, Itai & Shamir(1976)는 이진 변수와 쌍방향 제약으로 제약 만족 문제를 해결하기 위해 제한된 역추적을 포함하는 기술을 기술한다.그들은 이 기술을 수업 스케줄 문제에 적용하지만 2-SAT를 ^[5]포함한 다른 문제에도 적용된다고 관찰한다.

그들의 접근법의 기본 개념은 한 번에 한 변수씩 부분적인 진실 할당을 구축하는 것입니다.알고리즘의 특정 단계는 "선택 포인트"로, 변수에 두 가지 다른 진실 값 중 하나를 부여할 수 있는 지점이며 알고리즘의 이후 단계는 이러한 선택 포인트 중 하나로 역추적할 수 있습니다.그러나 가장 최근의 선택만 역추적할 수 있습니다.최근 선택보다 먼저 이루어진 모든 선택은 ^[5]영구적입니다.

처음에는 선택지가 없으며 모든 변수가 할당 해제됩니다.각 단계에서 알고리즘은 다음과 같이 값을 설정할 변수를 선택합니다.

• 양쪽 변수가 이미 설정되어 있는 절이 있는 경우, 그 절을 조작하는 방법으로 알고리즘은 가장 최근의 선택 포인트로 역추적하여 그 선택 이후 이루어진 할당을 취소하고 그 선택으로 이루어진 결정을 되돌립니다.선택 포인트가 없거나 알고리즘이 이미 최근 선택 포인트로 역추적된 경우 검색을 중단하고 입력 2-CNF 공식에 만족할 수 없음을 보고합니다.
• 절의 두 변수 중 하나가 이미 설정되어 있고 절이 여전히 true 또는 false가 될 수 있는 경우 다른 변수는 절을 강제로 true로 설정하는 방식으로 설정됩니다.
• 나머지 경우에는 나머지 변수가 어떻게 할당되든 각 절이 true가 되거나 두 변수 모두 아직 할당되지 않았습니다.이 경우 알고리즘은 새로운 선택 포인트를 생성하여 할당되지 않은 변수 중 하나를 임의로 선택한 값으로 설정합니다.

직관적으로 알고리즘은 각각의 선택을 한 후 모든 추론의 사슬을 따릅니다.이는 모순과 역추적 단계로 이어지거나, 모순이 도출되지 않으면 만족스러운 임무로 이어지는 올바른 선택이었다는 것을 의미한다.따라서 알고리즘은 만족스러운 할당을 올바르게 찾거나 입력이 ^[5]불만족스럽다고 올바르게 판단합니다.

심지어 이 알고리즘을 효율적으로 구현하는 방법에 대해서는 자세히 설명하지 않았다.이들은 "결정의 의미를 찾기 위해 적절한 데이터 구조를 사용"함으로써 알고리즘의 각 단계(백트래킹 제외)를 신속하게 수행할 수 있다고만 명시하고 있다.그러나 일부 입력으로 인해 알고리즘이 여러 번 역추적될 수 있으며, 그 때마다 역추적 전에 여러 단계를 수행하므로 전체 복잡성이 비선형적일 수 있습니다.이 문제를 피하기 위해 알고리즘을 변경하여 각 선택 포인트에 도달한 후 선택 포인트에서 설정된 변수에 대한 두 가지 할당의 테스트를 동시에 시작하고 두 가지 할당 각각에 동일한 수의 스텝을 소비합니다.이들 2개의 할당 중1개의 테스트에 의해 다른 선택 포인트가 생성되는 즉시 다른 테스트는 정지됩니다.따라서 알고리즘의 어느 단계에서나 테스트 중인 백트랙트리의 브랜치는 2개뿐입니다.이와 같이 변수에 대해 두 가지 검정을 수행하는 데 소요된 총 시간은 값이 영구적으로 할당된 입력 공식의 변수 및 구 수에 비례합니다.그 결과 알고리즘은 ^[5]총 선형 시간이 걸립니다.

견고하게 연결된 컴포넌트

Aspvall, Plass & Tarjan(1979)은 그래프 ^[4]이론에서 강하게 연결된 구성요소의 개념에 기초하여 2-만족도 인스턴스를 해결하기 위한 보다 단순한 선형 시간 절차를 발견했다.

유향 그래프의 두 꼭지점은 서로 강하게 연결되어 있다고 합니다.한쪽에서 다른 쪽으로의 유향 경로가 있는 경우 또는 그 반대쪽도 마찬가지입니다.이것은 동등성 관계이며 그래프의 정점은 강하게 연결된 구성요소, 즉 각 두 정점이 강하게 연결된 부분 집합으로 분할될 수 있습니다.깊이 우선 검색을 기반으로 그래프의 강하게 연결된 구성 요소를 찾기 위한 몇 가지 효율적인 선형 시간 알고리즘이 있습니다.Tarjan의 강력하게 연결된 컴포넌트^[7] 알고리즘과 경로 기반 스트롱 컴포넌트^[8] 알고리즘은 각각 단일 깊이 우선 검색을 수행합니다.Kosaraju 알고리즘은 먼저 두 가지 깊이 검색을 수행하지만 매우 간단합니다.

시사 그래프의 관점에서, 두 리터럴은 한 문자에서 다른 문자로의 시사 사슬이 존재할 때마다, 그리고 그 반대도 마찬가지의 강한 연결 요소에 속합니다.따라서 두 리터럴은 주어진 2-만족도 인스턴스에 대한 만족스러운 할당에서 동일한 값을 가져야 합니다.특히 변수와 그 부정 모두 강하게 연결된 동일한 구성요소에 속할 경우 이러한 두 리터럴에 동일한 값을 할당할 수 없기 때문에 인스턴스를 충족할 수 없습니다.Aspvall 등이 제시한 바와 같이, 이것은 필요하고 충분한 조건이다.^[4] 2-CNF 공식은 부정과 같은 강하게 연결된 구성요소에 속하는 변수가 없는 경우에만 만족할 수 있다.

이를 통해 즉시 2-CNF 공식의 만족도를 검사하는 선형 시간 알고리즘으로 이어집니다. 즉, 암시 그래프에서 강력한 연결 분석을 수행하고 각 변수와 해당 부정이 서로 다른 구성요소에 속하는지 확인합니다.그러나, Aspvall 등에서도 알 수 있듯이, 이는 또한 만족스러운 과제가 존재할 때 이를 찾기 위한 선형 시간 알고리즘으로 이어진다.알고리즘은 다음 단계를 수행합니다.

• 인스턴스의 시사 그래프를 작성하고 강력한 연결 분석을 위해 알려진 선형 시간 알고리즘을 사용하여 강하게 연결된 구성 요소를 찾습니다.
• 강하게 연결된 구성요소에 변수와 해당 부정이 모두 포함되어 있는지 확인합니다.이 경우 인스턴스가 만족스럽지 않다고 보고하고 중지합니다.
• u가 성분 i에 속하고 v가 성분 j에 속하도록 함축 그래프가 엣지 uv를 포함할 때마다 성분 i에서 성분 j까지의 엣지 uv를 가진 함축 그래프, 함축 그래프의 응축을 구성합니다.응축은 자동으로 방향 비순환 그래프이며, 응축이 형성된 암시 그래프와 마찬가지로 스큐 대칭입니다.
• 위상적으로 응축의 꼭지점을 정렬합니다.실제로는 코사라주의 알고리즘에 의해 위상순서로,^[9] 타잔의 알고리즘에 의해 역위상순서로 성분이 생성되기 때문에 이는 전 단계의 부작용으로 효율적으로 달성될 수 있다.
• 역위상 순서의 각 성분에 대해 해당 변수에 true가 할당되지 않은 경우 성분의 모든 리터럴을 true로 설정합니다.이로 인해 보완 컴포넌트의 모든 리터럴이 false로 설정됩니다.

역위상 순서와 스큐-대칭성으로 인해 리터럴이 참으로 설정되면 의미 사슬을 통해 리터럴에서 도달할 수 있는 모든 리터럴이 이미 참으로 설정되었습니다.대칭적으로 리터럴x 가 false 로 설정되어 있는 경우, 의미 사슬을 통해 리터럴x 로 이어지는 모든 리터럴은 이미 false 로 설정되어 있습니다.따라서 이 절차에 의해 구성된 진실 할당은 주어진 공식을 만족하며, 이는 또한 아스팔 등에 ^[4]의해 식별된 필요충분조건의 정확성 증명도 완료한다.

Aspvall 등이 나타내는 바와 같이, 함축 그래프의 강하게 연결된 성분들을 위상적으로 정렬하는 유사한 절차를 사용하여 정량화된 공식의 완전 정량화된 부울 ^[4]공식을 평가할 수도 있다.

적용들

기하학적 객체의 충돌 없는 배치

자동 라벨 배치 문제에 대한 정확하고 대략적인 알고리즘은 2가지 만족도에 기초하고 있습니다.이 문제는 다이어그램 또는 지도의 특징에 텍스트 레이블을 붙이는 것과 관련이 있습니다.일반적으로 각 라벨의 가능한 위치 세트는 맵 자체뿐만 아니라 서로에 의해 매우 제약됩니다(각 라벨은 라벨이 붙는 피쳐 근처에 있어야 하며 다른 피쳐를 가리지 않아야 합니다). 그렇지 않으면 두 라벨이 서로 겹치지 않도록 해야 합니다.일반적으로 이러한 제약을 따르는 라벨 배치를 찾는 것은 NP-하드 문제입니다.단, 각 피쳐의 라벨에 사용할 수 있는 위치가 2개(예를 들어 피쳐의 왼쪽과 오른쪽으로 확장)밖에 없는 경우 라벨 배치는 다항식 시간으로 해결할 수 있습니다.이 경우 라벨마다 변수가 있고 라벨 쌍마다 중복될 수 있는 절이 있는 2-만족성 인스턴스를 생성하여 위치가 중복되지 않도록 할 수 있습니다.라벨이 모두 일치하는 직사각형일 경우 대응하는 2-만족성 인스턴스는 선형적으로 많은 제약조건을 갖는 것으로 나타나 라벨링을 찾기 위한 ^[10]근선형 시간 알고리즘으로 이어질 수 있다.Poon, Zhu & Chin(1998)은 각 라벨이 라벨이 라벨이 있는 선 세그먼트에 대해 세 가지 위치 중 하나에 배치될 수 있는 직사각형인 지도 라벨링 문제를 기술하고 있습니다.각 라벨은 그 중 하나의 변으로 세그먼트를 가질 수도 있고 세그먼트의 중앙에 배치될 수도 있습니다.이들은 유효한 라벨링의 존재를 테스트하는 것이 2-만족도 ^[11]문제가 될 수 있도록 두 개의 이진 변수를 사용하여 이 세 가지 위치를 나타낸다.

Formann & Wagner(1991)는 각 라벨이 라벨링하는 점에 모서리 중 하나를 갖는 제약 조건으로 주어진 포인트 세트에 대해 가능한 가장 큰 크기의 정사각형 라벨을 찾는 문제에 대한 근사 알고리즘의 일부로 2-만족도를 사용한다.지정된 크기의 레이블을 찾기 위해 두 배일 경우 다른 점과 겹칠 수 있는 정사각형을 제거하고 다른 점의 레이블과 겹칠 수 없는 방식으로 레이블을 지정할 수 있는 점을 제거합니다.이러한 제거 규칙은 나머지 점의 라벨 배치를 점당 2개만 허용하므로 유효한 라벨 배치(존재하는 경우)를 2-만족도 인스턴스의 해결책으로 찾을 수 있음을 나타냅니다.해결 가능한 2-만족도 인스턴스로 이어지는 가장 큰 레이블 크기를 검색하여 최적의 솔루션보다 절반 이상 큰 레이블 배치를 찾습니다.즉, 알고리즘의 근사비는 최대 ^[10][12]2입니다.마찬가지로 각 라벨이 직사각형이고 라벨의 점이 아래쪽 가장자리를 따라 배치되어야 하는 경우, 2-만족도를 사용하여 각 라벨이 아래쪽 모서리에 점을 갖는 솔루션이 있는 가장 큰 라벨 크기를 구하면 최대 ^[13]2의 근사 비율이 됩니다.

다른 기하학적 배치 문제에 대해서도 2-만족도의 유사한 적용이 이루어졌다.그래프 그리기에서 정점 위치가 고정되고 각 가장자리가 가능한 두 위치 중 하나로 원형 호로 그려져야 하는 경우(예를 들어 호 다이어그램), 교차를 피하기 위해 각 모서리에 사용할 호를 선택하는 문제는 각 모서리에 대한 변수와 각 쌍의 구속조건에 대한 2-만족도 문제입니다.건널목으로 이어질 수 있는 장소들그러나 이 경우 암시 그래프를 ^[14]암묵적으로 검색함으로써 암시 그래프의 명시적 표현을 구축하고 검색하는 알고리즘에 비해 솔루션의 속도를 높일 수 있습니다.VLSI 집적회로 설계에서는 모듈 집합이 최대 한 번에 구부러질 수 있는 와이어로 접속해야 하는 경우 와이어에는 2개의 루트가 있으며, 모든 와이어를 회로의 단일 레이어로 라우팅할 수 있도록 이들 2개의 루트 중 어느 쪽을 사용할지를 선택하는 문제는 2-satiability로 해결할 수 있습니다.예를 들어 보겠습니다.^[15]

Boros et al.(1999)는 회로 설계에서 각 모듈을 미러 리버스할지 여부에 대한 또 다른 VLSI 설계 문제를 고려하였다.이 미러 반전에서는 모듈의 동작은 변경되지 않지만 모듈의 입력 및 출력 신호가 모듈에 연결되는 지점의 순서가 변경되어 모듈이 설계의 나머지 부분에 얼마나 잘 적합한지 변경될 수 있습니다.Boros 등에서는 모듈이 이미 단일 선형 채널을 따라 배치되어 모듈 간의 와이어가 배선되어야 하며 채널 밀도(채널의 단면을 통과해야 하는 신호의 최대 수)에 고정된 한계가 있는 문제의 단순화된 버전을 검토합니다.그들은 이 버전의 문제를 2가지 만족도의 인스턴스로 해결할 수 있다고 보고 있습니다.이 경우 제약조건은 서로 직접 채널을 가로지르는 모듈 쌍의 방향을 관련짓습니다.그 결과, 각 스텝이 2-만족도 인스턴스의 ^[16]해법을 수반하는 바이너리 서치를 실행함으로써 최적 밀도를 효율적으로 계산할 수도 있다.

데이터 클러스터링

메트릭 공간의 데이터 점 집합을 두 개의 클러스터로 클러스터링하는 한 가지 방법은 클러스터의 지름 합계를 최소화하는 방식으로 클러스터를 선택하는 것입니다. 여기서 단일 클러스터의 직경은 두 점 사이의 가장 큰 거리입니다.이는 최대 군집 크기를 최소화하는 것보다 더 바람직하며, 이로 인해 서로 다른 군집에 매우 유사한 점이 할당될 수 있습니다.두 군집의 목표 지름이 알려진 경우, 2-만족도 인스턴스를 해결함으로써 이러한 목표를 달성하는 군집을 찾을 수 있습니다.인스턴스(instance)에는 점당 변수가 하나씩 있어 해당 점이 첫 번째 클러스터에 속하는지 두 번째 클러스터에 속하는지 여부를 나타냅니다.두 점이 서로 너무 멀어서 동일한 클러스터에 속하지 못할 때마다 이 할당을 금지하는 절이 인스턴스에 추가됩니다.

개별 클러스터 직경을 알 수 없는 경우에도 동일한 방법을 서브루틴으로 사용할 수 있습니다.개별 군집 직경을 몰라도 주어진 직경의 합계를 얻을 수 있는지 여부를 테스트하기 위해 각 직경의 쌍을 2-만족도 인스턴스로 표현하고 2-만족도 알고리즘을 사용하여 b를 실현할 수 있는지 여부를 결정하는 최대 목표 직경 쌍을 모두 시도할 수 있습니다.y 클러스터화.지름의 최적 합계를 찾으려면 각 단계가 이 유형의 타당성 검정인 이항 검색을 수행할 수 있습니다.또한 클러스터 지름의 합계가 아닌 다른 조합을 최적화하고 메트릭 공간의 거리가 아닌 임의의 차등 번호를 ^[17]사용하여 클러스터의 크기를 측정하는 클러스터도 동일한 방법으로 찾을 수 있습니다.이 알고리즘의 시간 제한은 서로 밀접하게 관련된 일련의 2-만족성 인스턴스를 해결하는 시간에 의해 지배되며, Ramnath(2004)는 이러한 관련 인스턴스를 서로 독립적으로 해결했을 때보다 더 빨리 해결하는 방법을 보여줌으로써 총 Diamets clustere에 대한 시간 제한은³ O(n)가 된다.링 ^[18]문제

스케줄

심지어 Itai & Shamir(1976)는 n명의 교사를 각각 지도하도록 일정해야 하는 수업 스케줄 모델을 고려하고 있다.$선생님이$$코호트{\displaystyle }$j와 함께$$ $보내는$ 주당 시간은 문제에 대한 입력으로 $주어진{\displaystyle }$ 매트릭스 R$(\displaystyle$R_${ij})$의 ${\displaystyle {입력}_{}}$ R(\$displaystyle$ R_$${ij})에 의해 설명되며, 각 교사는 일정 시간을 사용할 수 있습니다.그들이 나타내듯이, 문제는 각 교사가 최대 3시간까지 가능한 경우에도 NP-완전이지만, 각 교사가 2시간만 가능한 경우 2만족도의 예로서 해결할 수 있습니다.(1시간만 가능한 교사는 문제에서 쉽게 제외될 수 있습니다.)이 문제에서 각 $변수{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{vi}}_{}}$j({$displaystyle v_{$ij})는$$ $교사{\displaystyle }$i(\$style$ i$)$가 $코호트{\displaystyle }$j(\$displaystyle$ j$)$와 함께 보내야 하는 시간에 대응하며, 변수에 대한 할당은 해당 시간이 교사의 참석 가능 시간 중 첫 번째인지 두 번째인지 여부를 지정합니다.또한 2개의 만족도 조항 pr이 있습니다.서로 동시에 교사에게 할당된 두 명의 코호트 또는 동시에 ^[5]두 명의 교사에게 할당된 한 명의 코호트 중 하나의 두 가지 유형의 충돌이 발생한 경우.

미야시로&마쓰이(2005)는 라운드 로빈 토너먼트의 페어링이 이미 결정되어 각 구장에 경기를 할당해야 하는 스포츠 스케줄의 문제에 대해서, 2개의 만족도를 적용하고 있다.이 문제에서는 한 팀이 두 번의 홈경기를 연속으로 치르는 '브레이크'를 피해 가능한 한 홈경기와 어웨이 경기를 번갈아 치르는 것이 바람직하다.대부분의 두 팀은 홈과 원정 경기를 번갈아 가면서 휴식을 완전히 피할 수 있다; 다른 어떤 팀도 이 두 팀만큼 홈 어웨이 일정을 가질 수 없다. 왜냐하면 그렇게 되면 같은 일정을 가진 팀과 경기를 할 수 없기 때문이다.따라서 최적의 스케줄은 두 개의 브레이크 없는 팀과 다른 팀마다 하나의 브레이크가 있다.브레이크리스 팀 중 하나를 선택하면 각 변수가 단일 게임에서 한 팀의 홈어웨이 할당을 나타내는 2가지 만족도 문제를 설정할 수 있으며, 제약조건에 따라 각 팀이 이전에 최대 1개의 브레이크와 최대 1개의 게임을 위해 일관된 할당이 이루어지는 특성이 적용됩니다.브레이크 없는 팀과의 경기 후에 브레이크가 있고, 두 번의 브레이크가 있는 팀은 없습니다.따라서 일정표에 최적의 휴식 횟수로 솔루션이 허용되는지 여부는 중단 없는 팀의 각 선택에 대해 하나씩 2가지 만족도 문제를 선형적으로 풀어 확인할 수 있습니다.비슷한 기술을 통해 각 팀이 한 번의 휴식 시간을 갖는 일정을 찾아 휴식 횟수를 최소화하는 대신 최대화할 수 있다.^[19]

이산 단층 촬영

단층촬영은 단면에서 형태를 회복하는 과정이다.자주 연구되어 온 문제의 단순화된 버전인 이산 단층촬영에서, 회복되는 모양은 폴리오미노(2차원 사각 격자의 정사각형 부분 집합)이며, 단면은 격자의 개별 행과 열의 정사각형 집합에 대한 집계 정보를 제공한다.예를 들어 숫자 또는 그리더에 의한 그림으로도 알려진 인기 있는 비도그램 퍼즐에서, 결정되는 정사각형 세트는 이진 이미지에서 어두운 픽셀을 나타내며, 퍼즐 해결사에 주어진 입력은 이미지의 각 행 또는 열에 얼마나 많은 어두운 픽셀을 포함하는지 그리고 각각의 길이를 알려준다.블록이 필요합니다.다른 형태의 디지털 단층 촬영에서는 각 행 또는 열에 대한 정보가 더 적게 제공됩니다. 즉, 정사각형 블록의 수와 길이보다는 총 정사각형 수만 제공됩니다.문제의 동등한 버전은 행렬의 각 행과 각 열에 있는 값의 합계만 주어진 주어진 0-1 행렬을 복구해야 한다는 것입니다.

주어진 행과 열의 ^[20]합계를 갖는 행렬을 찾는 다항식 시간 알고리즘이 존재하지만, 해답은 결코 유일하지 않을 수 있다. 즉, 2 × 2 항등 행렬 형태의 하위 행렬은 솔루션의 정확성에 영향을 주지 않고 보완될 수 있다.따라서 연구자들은 재구성할 형태에 대한 제약 조건을 탐색하여 솔루션의 공간을 제한하는 데 사용할 수 있습니다.예를 들어, 형상이 연결되어 있다고 가정할 수 있지만 연결된 솔루션이 있는지 여부를 검정하는 ^[21]것은 NP-완전입니다.보다 쉽게 해결할 수 있는 제약이 있는 버전은 모양이 직교 볼록하다는 것입니다. 즉, 각 행과 열에 하나의 연속된 정사각형 블록이 있습니다.Chrobak & Dür(1999)는 이전의 몇 가지 솔루션을 개선하여 2-SAT를 ^[22]사용하여 연결된 직교 볼록 형상을 효율적으로 재구성하는 방법을 보여주었다.이 솔루션의 아이디어는 재구성할 모양의 맨 왼쪽 및 맨 오른쪽 셀을 포함하는 행의 인덱스를 추측한 다음 이러한 추측과 주어진 행 및 열 합계와 일치하는 모양이 있는지 여부를 테스트하는 2-만족도 문제를 설정하는 것입니다.그들은 주어진 형상의 일부일 수 있는 각 정사각형에 대해 4개의 2-만족도 변수를 사용합니다. 하나는 그것이 형상의 가능한 네 개의 "구석 영역" 각각에 속하는지 여부를 나타내기 위한 변수입니다. 그리고 그들은 이러한 영역을 분리하도록 강요하고, 원하는 모양을 가지도록 하며, 연속된 행과 열로 전체 형상을 형성하도록 하는 제약 조건을 사용합니다.원하는 행과 열의 합계를 구합니다.이들의 알고리즘에는 시간 O(mn³)가 소요됩니다.여기서 m은 입력 형상의 2차원 중 작은 것이고 n은 2차원 중 큰 것입니다.같은 방법은 나중에 직교 ^[23]연결 대신 대각선으로만 연결될 수 있는 직교 볼록 형상으로 확장되었습니다.

완전한 비그램 퍼즐의 솔버의 일부인 바텐버그와 코스터스(2008, 2009)는 여러 다른 휴리스틱에서 얻은 정보를 결합하기 위해 2-만족도를 사용했다.퍼즐에 대한 부분적인 해답이 주어진 경우, 각 행 또는 열 내의 동적 프로그래밍을 사용하여 해당 행 또는 열의 제약으로 인해 정사각형이 흰색 또는 검은색으로 강제되는지 여부 및 동일한 행 또는 열에 있는 두 개의 정사각형이 암시 관계에 의해 연결될 수 있는지 여부를 결정합니다.그들은 또한 각 행과 열의 블록 길이의 시퀀스를 합으로 대체함으로써 비 도표를 디지털 단층 촬영 문제로 변환하고, 이 모든 행과 열을 결합하는 디지털 단층 촬영 문제가 상태를 결정할 수 있는 정사각형 또는 정사각형 쌍을 가질 수 있는지 결정하기 위해 최대 흐름 공식을 사용합니다.암묵적인 관계에 의해 연결되어 있습니다.이 두 가지 경험적 통계학 중 하나가 제곱 중 하나의 값을 결정하면 부분 솔루션에 포함되고 동일한 계산이 반복됩니다.그러나 양쪽 휴리스틱이 제곱을 설정하지 못한 경우, 양쪽에서 발견된 암시를 2-만족도 문제로 결합하고 2-만족도 솔버를 사용하여 문제에 의해 값이 고정된 제곱을 구하며, 그 후 절차를 반복한다.이 절차는 솔루션을 찾는 데 성공할 수도 있고 그렇지 않을 수도 있지만 다항식 시간에 실행되도록 보장합니다.Batenburg과 Kosters는 대부분의 신문사 퍼즐, 샤미르(1976년)[5]가 훨씬 더 동적 프로그래밍과 흐름의 발견적 학습 법보다 효과적이다 전체 전력은 이 절차와 심지어, Itai &amp의 제한된 backtracking과 이2-satisfiability 접근법을 결합한 더 많지만 느린 강력한 절차를 필요로 하지 않는다 보고하고 있다.without 2-불확실성, 랜덤으로 생성된 보다 어려운 ^[24]비그래픽에 적용할 경우.

이름 변경 가능한 경음기 만족도

2-만족도 다음으로, 다항식 시간에 해결할 수 있는 만족도 문제의 또 다른 주요 하위 클래스는 뿔-만족도이다.만족도 문제의 이 클래스에서 입력은 다시 결합 정규 형식의 공식입니다.절당 임의로 리터럴 수를 가질 수 있지만 최대 1개의 양의 리터럴을 가질 수 있습니다.루이스(1978)는 보조 2-만족도 사례를 통해 다항식 시간 내에 해결할 수 있는 이 클래스의 일반화, 다시 이름 붙일 수 있는 혼 만족도를 발견했다.일부 변수를 부정으로 대체하여 경음기 형태로 만들 수 있는 공식은 경음기입니다.이를 위해 Lewis는 이름 변경 가능한 Horn 인스턴스의 각 변수에 대해 하나의 변수를 사용하여 2-만족도 인스턴스를 설정합니다. 여기서 2-만족도 변수는 대응하는 이름 변경 가능한 Horn 변수를 부정할지 여부를 나타냅니다.Horn 인스턴스를 생성하기 위해서는 이름 변경 가능한 Horn 인스턴스의 같은 절에 나타나는 두 개의 변수가 해당 절에 긍정적으로 표시되지 않아야 합니다. 변수 쌍에 대한 이 제약 조건은 2-만족도 제약 조건입니다.Lewis는 결과적인 2-만족도 인스턴스에 대한 만족스러운 할당을 찾아냄으로써 이름을 다시 지을 수 있는 Horn 인스턴스를 다항식 시간에 ^[25]Horn 인스턴스로 전환하는 방법을 보여줍니다.긴 절을 여러 개의 작은 절로 분할하여 선형 시간 2-만족도 알고리즘을 적용함으로써 이를 선형 ^[26]시간으로 줄일 수 있다.

기타 응용 프로그램

2-유향성은 또한 독립적인 집합과 소수의 완전한 초당 하위 ^[27]그래프로 분할될 수 있는 무방향 그래프를 인식하는 문제, 인터넷의 ^[28]자율 하위 시스템 간의 비즈니스 관계를 추론하고 진화적 ^[29]트리를 재구성하는 문제에도 적용되었다.

복잡성과 확장

NL 완전성

쓰기 가능한 메모리의 대수적 양만을 사용하여 2-suffiability 인스턴스가 만족스럽지 않은지 여부를 판단하기 위한 비결정적 알고리즘은 쉽게 설명할 수 있습니다. 즉, 변수 v를 선택하고 v에서 부정으로 이어지는 일련의 시사점을 검색(비결정적)한 다음 v로 되돌아가는 것입니다. 이러한 경우입니다.instance는 만족할 수 없습니다.Immerman-Szelepcsényi 정리에 의해, 또한 비결정론적 로그 공간에서 만족스러운 2-만족성 인스턴스가 충족되는지 검증할 수 있다.

2-만족도는 NL-완전입니다.^[30] 즉, 로그 공간에서 비결정적으로 해결할 수 있는 문제의 복잡도 클래스 NL에서 "가장 어려운" 문제 또는 "가장 표현적인" 문제 중 하나입니다.여기서 완전성은 로그 공간만을 사용하는 결정론적 튜링 기계가 NL의 다른 모든 문제를 동등한 2-만족도 문제로 변환할 수 있다는 것을 의미합니다.더 잘 알려진 복잡도 클래스 NP에 대한 유사한 결과와 유사하게, 이 변환은 Immerman-Szelepcsényi 정리와 함께 NL의 모든 문제를 길이 2로 제한된 하나의 존재하는 수량화된 술어와 함께 2차 논리식으로 나타낼 수 있게 한다.이러한 공식은 SO-Krom으로 ^[31]알려져 있다.마찬가지로 함축적 정규형은 전이적 ^[31]폐쇄를 위한 연산자를 추가하여 1차 논리로 표현될 수 있다.

모든 솔루션 세트

2-만족도 인스턴스(instance)에 대한 모든 솔루션 집합은 중앙값 그래프 구조를 가지며, 여기서 가장자리는 서로 같거나 같지 않도록 제약된 변수 집합의 값을 뒤집는 작업에 해당합니다.특히 이러한 방법으로 가장자리를 따라가면 어떤 솔루션에서 다른 솔루션으로 이동할 수 있습니다.반대로 중앙값 그래프는 이러한 방식으로 2-만족도 인스턴스에 대한 솔루션 집합으로 나타낼 수 있습니다.세 솔루션의 중위수는 각 변수를 세 솔루션의 대부분에 있는 값으로 설정하여 형성됩니다.이 중위수는 ^[32]항상 인스턴스에 대한 다른 솔루션을 형성합니다.

Feder(1994)는 주어진 2-만족도 인스턴스에 대한 모든 솔루션을 효율적으로 나열하고 몇 가지 관련 ^[33]문제를 해결하기 위한 알고리즘을 설명한다.또한 서로 ^[34]최대 해밍 거리를 갖는 두 가지 만족스러운 과제를 찾기 위한 알고리즘이 존재합니다.

만족할 수 있는 과제 수 계산

#2SAT는 주어진 2-CNF 공식에 대한 만족할 수 있는 할당 수를 계산하는 문제입니다.이 계산 문제는#P-complete,[35]는지 않는 한 P는 NP이다. 게다가,#2SAT에 대한 완전히 다항식 임의적인 근사 계획 입력 2-CNF 공식 monotone로 제한되지 않는 한 NP=RP고 심지어는 보유하고 있는 즉, 2-CNF 공식 각 리터럴은 긍정적인 occurr는 다항 시간에 풀 수 있는지 않을 것이란 얘기다.enc변수의 ^[36]e.

2SAT 공식에 대한 정확한 할당 수를 계산하는 가장 빠른 알고리즘은 $시간{\displaystyle }$O(1${\displaystyle {\mathrm{.}}^{2377}}$ n$)$ {$displaystyle$O($1.2377^{n$^[37]에서 ${\displaystyle {}^{}}$됩니다.

랜덤 2-만족도 인스턴스

가능한 모든 2-변수 구 집합에서 각 구를 랜덤으로 선택함으로써 주어진 변수 수 n과 절 m에 대해 무작위로 2-만족도 인스턴스를 형성할 수 있다.m이 n에 비해 작을 경우 이러한 인스턴스는 충족될 가능성이 높지만 m 값이 클수록 충족될 확률이 낮아집니다.보다 정확하게는 m/n이 상수α δ1로 고정되면 n이 무한대로 갈수록 충족가능성이 한계에 도달하는 경향이 있다.α < 1이면 한계가 1이고 α > 1이면 한계가 0이다.따라서 이 문제는 α = ^[40]1에서 위상 전이를 나타낸다.

최대 2가지 만족도

Maximum-2-satisable problem(MAX-2-SAT)에서 입력은 절마다 2리터씩의 결합 정규식이며 할당에 의해 동시에 충족될 수 있는 절의 최대 수를 결정하는 것이 과제입니다.보다 일반적인 최대 만족도 문제와 마찬가지로 MAX-2-SAT는 NP-hard입니다.그 ^[41]증거는 3SAT에서 축소된 것이다.

MAX-2-SAT를 제1 서브셋과 제2 서브셋에 1개의 엔드포인트를 갖는 에지 수와 제2 서브셋에 1개의 엔드포인트를 갖는 에지 수를 최대화하는 문제로서 공식화하고, 이 컷 문제에 반정의 프로그래밍 방법을 적용함으로써 핀 접속이 가능하다.d 다항식 시간에서 최소 0.940을 만족하는 근사해...최적의 ^[42]절 수를 곱한 값입니다.균형 잡힌 MAX 2-SAT 인스턴스는 모든 변수가 동일한 가중치로 양수 및 음수로 표시되는 MAX 2-SAT 인스턴스입니다.이 문제에 대해 Austrin은 근사비를 최소${\displaystyle \{}$ (${\displaystyle 3}$ - ${\displaystyle \cos }$-${\displaystyle {}^{-}}$ )${\displaystyle {}^{}}$- ${\displaystyle 1}$(${\displaystyle }$2 + (${\displaystyle 2}$ /${\displaystyle }$) )${\displaystyle }$） :${\displaystyle 2\mathrm{}}$ / 2${\displaystyle \pi }$ ${\displaystyle \pi }$} ${\displaystyle \}}$ } ${\displaystyle \mathrm{=}}$ 0.${\displaystyle \mathrm{943...}}$로 개선했습니다.$\displaystyle \left\{(3-\cos \theta)^{-1}(2+(2/\pi)\theta),:,\pi / 2\leq \theta \leq \leq \pi \right\}= 0.943...$$\}.$^[43]

고유한 게임 추측이 참일 경우, 0.943보다 나은 근사 상수로는 균형 여부에 관계없이 MAX 2-SAT를 근사하는 것이 불가능하다.다항식 시간으로.^[44]P np NP라는 더 약한 가정 하에서 이 문제는 21/22 = 0.95454보다 ^[45]좋은 상수 내에서만 측정 불가능한 것으로 알려져 있습니다.

다양한 저자들은 또한 MAX-2-SAT ^[46]인스턴스의 정확한 솔루션을 위해 기하급수적으로 최악의 경우 시간 범위를 조사했다.

가중치-2-만족도

Weighted 2-safficibility Problem(W2SAT; 가중치 2-safficibility 문제)에서는 입력은 n$\displaystyle$ n$}$ $변수$ 2SAT 인스턴스와 정수 k가 됩니다.문제는 변수 중 정확히 k가 ^[47]참인 만족스러운 할당이 존재하는지 판단하는 것입니다.

W2SAT 문제는 특별한 경우로서 주어진 무방향 그래프의 모든 모서리에 함께 닿는 k개의 정점 세트를 찾는 정점 커버 문제를 포함한다.정점 커버 문제의 특정 인스턴스에 대해 그래프의 각 정점에 대해 변수를 사용하여 동등한 W2SAT 문제를 구성할 수 있습니다.그래프의 각 가장자리 uv는 솔루션의 참 변수 중 u 또는 v를 포함해야만 충족될 수 있는 2SAT 절 u δ v로 나타낼 수 있다.그런 다음 결과 2SAT 공식의 만족스러운 인스턴스는 정점 커버 문제에 대한 솔루션을 인코딩하고, k개의 정점이 있는 정점 커버가 있는 경우에만 k개의 참 변수를 만족시키는 할당이 있다.따라서 정점 커버와 마찬가지로 W2SAT는 NP-완전입니다.

더욱이, 매개 변수화된 복잡도에서 W2SAT는 자연스러운 W[1]-완전 ^[47]문제를 제공하는데, 이는 W2SAT가 W[1]의 모든 문제에 적용되지 않는 한 W2SAT는 고정 매개 변수 추적이 불가능하다는 것을 의미한다.즉, 실행 시간이 f(k)·n^O(1) 형식인 W2SAT 알고리즘이 존재할 가능성은 거의 없습니다.더욱 강력한 것은 지수 시간 가설이 ^[48]실패하지 않는 한 W2SAT는 시간^o(k) n에 해결될 수 없다는 것입니다.

정량화된 부울 공식

크롬(1967)은 2-만족도를 위한 첫 번째 다항식-시간 알고리즘을 찾는 것 외에도, 양자화되는 공식이 2-CNF 공식인 완전 양자화된 부울 공식을 평가하는 문제를 공식화했다.2-만족도 문제는 이 정량화된 2-CNF 문제의 특수한 경우로, 모든 수량화자가 존재합니다.크롬은 또한 이러한 공식에 대한 효과적인 결정 절차를 개발했다.Aspvall, Plass & Tarjan(1979)은 강력하게 연결된 컴포넌트와 토폴로지 ^[2][4]순서를 확장함으로써 선형 시간 내에 해결할 수 있음을 보여주었다.

다치 로직

2-만족도 문제는 제안적 다치 논리에도 요청될 수 있다.알고리즘은 보통 선형적이지 않으며 일부 로직에서는 NP-완전인 경우도 있습니다.설문조사는 ^[49]Hénle(2001, 2003)를 참조한다.

레퍼런스