제약 조건 만족도의 복잡성

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2011년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

제약조건 만족도의 복잡성은 제약조건 만족도에 대한 계산 복잡성 이론의 적용이다.그것은 주로 유한영역의 제약만족 문제에서 다루기 쉬운 계층과 다루기 힘든 계층을 구별하기 위해 연구되어 왔다.

유한영역에서 제약 만족 문제를 해결하는 것은 일반적으로 NP-완전성 문제다.연구에 따르면 다항 시간 하위 케이스는 대부분 허용된 영역 또는 제약 조건 또는 변수 위에 제약 조건을 배치할 수 있는 방법을 제한함으로써 얻어진다.또한 연구에서는 제약 만족 문제와 유한 모델 이론과 데이터베이스와 같은 다른 영역의 문제 사이의 관계를 확립했다.

개요

유한 영역의 제약조건 만족도 문제가 해결책이 있는지 여부를 확인하는 것은 일반적으로 NP 완전한 문제다.이것은 제약조건 만족도 문제로서 표현 가능한 많은 다른 NP 전체 문제의 쉬운 결과물이다.그러한 다른 문제들에는 명제적 만족도와 3색상이 포함된다.

견인성은 제약 만족도 문제의 특정 계층을 고려함으로써 얻을 수 있다.예를 들어 도메인이 2진수이고 모든 제약조건이 2진수인 경우 만족도를 설정하는 것은 다항시간제 문제인데, 이 문제는 2-SAT와 동일하기 때문이다.연구 결과, 다루기 쉬운 많은 하위 케이스가 발견되었다.이러한 세분류 중 일부는 허용된 도메인이나 관계를 제한하고, 일부는 변수에 제약이 가해지는 방법을 제한하며, 일부는 두 가지 종류의 제한에 기초한다.

한 연구 라인은 제약 만족 문제와 두 관계 구조 사이에 동형성의 존재를 확립하는 문제 사이의 대응 관계를 사용했다.이 서신은 제약조건 만족도를 전통적으로 데이터베이스 이론과 관련된 주제와 연결하기 위해 사용되어 왔다.

고려된 연구 문제는 일련의 제한들 사이에 이분법의 존재에 관한 것이다.이는 일련의 제한사항이 다항 시간 제한과 NP-완전 제한만을 포함하고 있는지에 대한 문제다.이 질문은 몇 가지 제한에 대해 해결되었지만, 2007년^[update] 현재 고정된 영역과 관계 세트에 기초한 모든 제한에 대해서는 여전히 개방되어 있다.이것은 제약조건 만족도의 복잡성에 대한 가장 중요한 공개 질문으로 일부 저자들은 간주한다.

제한사항

일반적인 제약조건 만족도 문제의 다루기 쉬운 하위 사례는 해당 문제에 적절한 제한을 가함으로써 얻을 수 있다.다양한 제한이 검토되었다.

구조적 및 관계적 제약

추적성은 가능한 영역이나 제약조건을 제한함으로써 얻을 수 있다.특히 다음과 같은 두 가지 종류의 제한이 검토되었다.

• 관계 제한은 영역과 제약 조건을 만족하는 값을 제한한다.
• 구조적 제한은 제약 조건이 변수에 분산되는 방식을 제한한다.

더 정확히 말하면, 관계 제한은 제약 언어를 지정하는데, 이것은 도메인이고 이 도메인에 대한 일련의 관계다.제약조건 만족도 문제는 그것이 정확히 이 영역을 가지고 있고 각 제약조건의 관계가 주어진 관계 집합에 있는 경우 이 제한을 충족한다.즉, 관계적 제약은 영역과 각 제약조건의 만족 값 집합을 제한하지만 제약조건이 변수 위에 어떻게 배치되는지는 제한하지 않는다.이것은 대신에 구조적인 제약에 의해 이루어진다.구조적 제약은 제약 조건의 범위(변수)만 보고 그들의 관계(만족 가치의 집합)를 무시하면 확인할 수 있다.

제약조건 언어는 언어, 즉 도메인에 지정된 도메인과 관계를 사용하여 모든 문제를 해결하는 다항식 알고리즘이 존재하는 경우 추적 가능하다.추적 가능한 제약 조건 언어의 예로는 이진 영역과 이진 제약 조건이 있다.공식적으로, 이 제한은 크기가 2인 도메인과 이진 관계인 제약 조건만 허용하는 것에 해당한다.두 번째 사실은 제약조건의 범위가 이항이라는 것을 의미하지만, 이것은 임의의 변수 쌍에 어떤 제약조건이 배치되는 것을 금지하지 않기 때문에 구조적 제약이 아니다.우발적으로, 두 가지 제한이 해제되면 문제는 NP가 완성된다. 이항 구속조건과 3항 도메인은 그래프 색칠 문제를 나타낼 수 있고, 이항 구속조건과 2항 도메인은 3-SAT를 나타낼 수 있다. 이 두 가지 문제는 모두 NP-완전이다.

구조 제한의 관점에서 정의된 추적 가능한 클래스의 예는 이항 반복 문제의 클래스다.이항 구속조건에 대한 제약조건 만족도 문제를 고려할 때, 관련 그래프는 모든 변수에 대한 정점과 모든 구속조건에 대한 가장자리를 가지고 있다. 두 꼭지점이 구속조건에 있을 경우 결합된다.문제의 그래프가 반복적인 경우, 그 문제도 또한 반복적인 것으로 불린다.2진법 반복문제의 등급에 대한 만족도 문제는 다루기 쉽다.이는 제약조건을 충족하는 특정 값이나 도메인에 제한을 두지 않고 오히려 제약조건이 변수 위에 배치되는 방식을 제한하기 때문에 구조적 제약이다.

관계적, 구조적 제약이 주로 제약 만족도의 추적 가능한 클래스를 도출하는 데 사용되는 반면, 일부 추적 가능한 클래스는 관계적 제약 또는 구조적 제약만으로 정의될 수 없다.행 대류도 관계와 변수의 순서에 따라 달라지기 때문에 행 대류도 관점에서만 정의하거나 구조적인 측면에서만 정의될 수 없다(따라서 각 제약조건만을 차례대로 살펴봐야 확인할 수 없다).

균일 및 불균일 제한

한정된 제약조건 언어로 제한하여 얻은 하위사례를 불균일 문제라 한다.이러한 문제들은 아래에 설명한 바와 같이 동형문제의 관점에서 제약 만족도를 표현할 때 주로 고려된다.균일한 문제는 동형성 문제의 설정에서도 정의되었다. 균일한 문제는 불균일한 문제의 (아마도 무한한) 집합의 결합으로 정의될 수 있다.이 모든 통일되지 않은 문제들이 다루기 쉬울지라도, 무한히 통일되지 않은 문제들로 이루어진 통일적인 문제는 다루기 힘들 수 있다.

트리 기반 제한

일부 제한사항은 제약조건이 모두 이항이고 변수 위에 트리를 형성하는 제약조건 만족도 문제의 견인성에 기초한다.이는 제약의 범위만을 보고 도메인과 관계를 무시한 채 확인할 수 있는 구조적인 제약이다.

이 제한은 문제의 원시 그래프를 기반으로 하는데, 이 그래프는 문제의 정점이 문제의 변수인 그래프와 가장자리가 두 변수 사이의 제약조건의 존재를 나타낸다.그러나 나무라는 조건을 원래 문제의 원초적 그래프에 배치함으로써 트랙터성도 얻을 수 있다.

등가조건

제약조건 만족도 문제는 다른 문제들의 관점에서 개편될 수 있으며, 트랙터블과 동등한 조건으로 이어질 수 있다.가장 많이 사용되는 개혁은 동형문제의 문제라는 관점이다.

제약 만족도와 동형성 문제

제약조건 만족도와 데이터베이스 이론 사이의 연계는 제약조건 만족도 문제와 두 관계 구조 사이에 동형성이 존재하는지 확인하는 문제 사이의 대응의 형태로 제공되었다.관계 구조는 데이터베이스의 수학적인 표현이다: 그것은 가치들의 집합이고 이러한 가치들에 대한 관계의 집합이다.Formally, ${\displaystyle A=(V,R_{1}^{A},\ldots ,R_{n}^{A})}$, where each ${\displaystyle R_{i}^{A}}$ is a relation over ${\displaystyle V}$, that is, a set of tuples of values of ${\displaystyle V}$.

관계 구조는 제약조건 만족도 문제와 다르다. 제약조건은 변수들의 관계와 튜플이기 때문이다.또한 제약 만족도 문제의 경우 만족스러운 과제를 찾는 것이 주요 문제이고 관계 구조의 경우 질의에 대한 답을 찾는 것이 주요 문제라는 점도 다르다.

그러나 제약 만족 문제는 두 관계 구조 사이에 동형성의 존재를 확립하는 문제와 관련이 있다.동형성(同形性)은 첫 번째 관계의 값에서 두 번째 구조의 모든 관계에 적용되었을 때 두 번째 구조의 해당 관계의 하위 집합으로 만드는 두 번째 값의 함수다.Formally, ${\displaystyle h}$ is a homomorphism from ${\displaystyle A=(V,R_{1}^{A},\ldots ,R_{n}^{A})}$ to ${\displaystyle B=(D,R_{1}^{B},\ldots ,R_{n}^{B})}$ if it is a function from ${\displaystyle V}$ to ${\displaystyle D}$ such that, if ${\displaystyle (x_{1},\ldots ,x_{k})\in R_{i}^{A}}$ then ${\displaystyle (h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}}$.

제약 만족 문제와 동형상 문제 사이의 직접적인 대응은 성립될 수 있다.주어진 제약조건 만족 문제에 대해서는, 한 쌍의 관계 구조, 첫 번째 변수 및 제약조건의 서명을 인코딩하는 구조, 두 번째의 도메인 인코딩과 제약조건의 관계를 구축할 수 있다.제약조건 만족도 문제의 만족도는 서명의 값을 대체하면 제약조건과 관련된 튜플이 될 수 있는 모든 변수에 대한 값을 찾는 것에 해당한다.이는 이 평가가 두 관계 구조 사이의 동형성일 경우 정확히 가능하다.

역적 대응은 반대다: 두 개의 관계 구조를 주어, 하나는 제약 만족 문제의 변수에 있는 첫 번째의 값과 같은 문제의 영역에 있는 두 번째 값의 값을 부호화한다.첫 번째 구조의 모든 관계에 대한 모든 튜플에는 두 번째 구조의 통신원 관계를 가치로 삼는 제약조건이 있다.이러한 방식으로 동형성은 모든 제약조건의 모든 범위(첫 번째 구조물의 모든 관계에서 모든 튜플)를 제약조건의 관계에서 튜플(두 번째 구조물의 해당 관계에 있는 튜플)로 매핑하는 것에 해당한다.

불균일 제약 만족 문제는 동형성 문제의 두 번째 구조가 고정된 제한이다.즉, 모든 관계 구조는 불균일한 문제, 즉 관계 구조가 그것에 동형성이 있는지를 말해주는 문제를 정의한다.첫 번째 구조에도 유사한 제약을 둘 수 있다. 어떤 고정된 첫 번째 구조물에 대해서도 동형상 문제는 다루기 쉽다.균일한 제약 만족 문제는 동형성 문제의 제1구조와 제2구조물에 대한 구조 집합에 대한 임의적인 제한이다.

접속 질의 평가 및 격납

동형성 문제는 결막 질의 평가와 결막 질의 억제에 해당하기 때문에 이 두 가지 문제는 제약 만족도에도 해당된다.

평가 참여

모든 제약조건은 데이터베이스에서 표로 볼 수 있으며, 여기서 변수는 속성 이름으로 해석되고 관계는 표의 레코드 집합이다.제약조건 만족도 문제의 해결책은 그 제약조건을 나타내는 표의 내부 결합의 결과로서, 따라서 다수의 표의 내부 결합의 결과가 비어 있는가를 확인하는 문제로서 해결책 존재의 문제를 재구성할 수 있다.

이분법적 정리

일부 제약 언어(또는 통일되지 않은 문제)는 다항식 시간에 해결할 수 있는 문제와 대응되는 것으로 알려져 있으며, 그 외 다른 것들은 NP-완전한 문제를 표현하는 것으로 알려져 있다.그러나, 일부 제약 언어들은 둘 다 아닐 수도 있다.P가 NP와 같지 않으면 NP에 다항시간도 NP-하드도 아닌 문제가 존재한다는 것은 래드너의 정리에 의해 알려져 있다.2007년^[update] 현재, 이러한 문제가 고정된 제약조건 언어의 제약조건 만족 문제로 표현될 수 있을지는 알 수 없다.만약 라드너 언어가 이런 식으로 표현할 수 없다면, 모든 제약조건 언어의 집합은 다항 시간을 정의하는 언어와 NP-완전한 문제를 정의하는 언어로 정확히 나눌 수 있을 것이다. 즉, 이 집합은 이분법을 나타낼 것이다.

일부 결과는 일부 제약 언어 집합에 대해 알려져 있다.그러한 결과는 가장 잘 알려진 샤이퍼의 이분법 정리인데, 이는 이진영역의 제약 언어 집합에서 이분법의 존재를 증명한다.좀 더 정확히 말하면, 그것은 이진영역에 대한 관계제한이 그것의 모든 관계가 6개 등급 중 하나에 속할 경우 추적가능하고, 그렇지 않을 경우 NP-완전하다는 것을 증명한다.불라토프는 세 가지 요소의 영역에 대한 이분법적 정리를 증명했다.

제약 언어에 대한 또 다른 이분법적 정리로는 헬-네세트리얼 정리인데, 단일 고정 대칭관계로 이진 제약에 관한 문제에 대한 이분법을 보여준다.동형문제의 관점에서, 그러한 모든 문제는 관계 구조에서 주어진 고정된 비방향 그래프에 이르는 동형문제의 존재와 동등하다(비방향 그래프는 단일 이항 대칭 관계를 갖는 관계 구조로 간주할 수 있다).헬-네세트리올 정리는 그러한 모든 문제가 다항식 시간이나 NP-완전이라는 것을 증명한다.더 정확히 말하면, 문제는 그래프가 2색일 경우 다항식 시간, 즉 초당적이고 그렇지 않으면 NP 완성이다.

트랙터블을 위한 충분한 조건

일부 복잡성 결과는 동일한 종류의 다른 가능한 모든 제한사항이 NP-hard라는 것을 증명하지 않고 일부 제한사항이 다항식이라는 것을 증명한다.

데이터로그

트랙터블에 대한 충분한 조건은 데이터로그의 표현성과 관련이 있다.부울 데이터로그 쿼리는 주어진 알파벳에 걸쳐 일련의 리터럴에 진실 값을 부여하며, 각 리터럴은 $L{\displaystyle }$(${\displaystyle {1\mathrm{}}_{},}$… , ${\displaystyle n_{}}$)$${\$displaystyle L(a_{1},\ldots ,a_{n}}}}$ 형식의 표현이다$.$ 그 결과 부울 데이터로그 쿼리는 모든 리터럴 집합의 집합과 의미상 동등한 것으로 간주될 수 있기 때문이다.사실대로 평가되는 일련의 문학 작품들

반면 통일되지 않은 문제는 비슷한 세트를 표현하는 방법으로 볼 수 있다.주어진 통일되지 않은 문제의 경우, 제약에 사용될 수 있는 관계 ${\displaystyle {세트}_{}}$는 고정되어 있다. 그 결과, $R{\displaystyle {}_{}}$ ${\displaystyle 1_{}}$,${\displaystyle \dots ,}$ R ${\displaystyle {}_{}}$ ${\$을 그들에게 고유한$$ 이름으로 줄 수 있다.이 통일되지 않은 문제의 예는 ${\displaystyle {Ri}_{}{x\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$… ,${\displaystyle }$x ${\displaystyle n_{}}$) ${\displaystyle R_{i}(x_{1},\ldots,x_{n})$ 형식의 리터럴 집합으로 기록될 수 있다$.$ 이러한 인스턴스들/리터럴 집합 중 일부는 만족스럽고 일부는 만족스럽지 않다; 리터럴 집합이 지정된 관계에 따라 충족될 수 있다.그는 비문제.반면에 통일되지 않은 문제는 어떤 리터럴이 만족스러운 예시를 나타내고 어떤 리터럴이 만족스럽지 못한 예시를 나타내는지 알려준다.일단 관계가 명명되면, 통일되지 않은 문제는 일련의 리터러시들을 표현한다: 만족스러운 (또는 만족스럽지 못한) 예들과 관련된 리터러시들.

추적가능성의 충분한 조건은 불만족스러운 인스턴스 집합이 부울 데이터로그 쿼리에 의해 표현될 수 있는 경우 불균일한 문제를 추적할 수 있다는 것이다.즉, 통일되지 않은 문제의 불만족스러운 예를 나타내는 리터럴 집합도 부울 데이터로그 쿼리를 충족하는 리터럴 집합이라면, 통일되지 않은 문제는 다루기 쉽다.

국소 일관성

만족도는 때때로 지역 일관성의 형태를 시행한 다음 빈 도메인이나 제약 관계의 존재를 확인함으로써 확립될 수 있다.이것은 일반적으로 정확하지만 불완전한 불만족 알고리즘이다: 문제는 빈 영역이나 제약 관계가 생성되지 않더라도 불만족스러울 수 있다.일부 형태의 국부적 정합성의 경우, 이 알고리즘에는 지수적 시간도 필요할 수 있다.그러나 일부 문제와 지역 일관성의 경우 정확하고 다항식 시간이다.

다음 조건은 문제의 원시 그래프를 이용하는데, 이 그래프는 각 변수에 대한 정점과 해당 변수가 제약조건에 있을 경우 두 노드 사이에 에지가 있다.지역적 일관성을 강제할 수 있고 만족도를 확립할 수 있는 이진 제약 조건 만족 문제에 대한 조건은 다음과 같다.

1. 원시 그래프가 반복적인 경우 호 일관성 적용
2. 너비가 1인 제약 조건의 순서 그래프를 만드는 변수의 순서에 대한 방향 호 일관성 적용(원초 그래프가 트리인 경우 및 나무의 모든 순서가 1을 생성하는 것은 아닌 경우에만 그러한 순서가 존재함)
3. 유도 폭 2를 갖는 원시 그래프를 만드는 변수의 순서에 대해 강한 방향 경로 일관성을 시행한다.

비이항 구속조건 만족도 문제에 대해 마지막을 연장하는 조건.즉, 원시 그래프가 일정한 i로 경계를 이루도록 유도하는 순서가 존재하는 모든 문제에 대해 강한 방향 i-일관성을 강제하는 것은 다루기 쉬우며 만족도를 확립할 수 있다.

트리 기반 조건

이항 제약조건으로 구성된 제약조건 만족도 문제는 그래프로만 볼 수 있는데, 여기서 정점은 변수이고 가장자리는 두 변수 사이의 제약조건의 존재를 나타낸다.이 그래프를 문제의 Gaifman 그래프 또는 원시 제약 그래프(또는 단순히 원시 그래프)라고 한다.

문제의 초기 그래프가 반복적인 경우, 문제의 만족도를 설정하는 것은 다루기 쉬운 문제다.이는 제약의 범위만을 보고 그들의 관계와 도메인을 무시한 채 확인할 수 있는 구조적인 제약이다.Acyclic 그래프는 숲이지만 연결성이 보통 가정된다. 그 결과, 일반적으로 원시 그래프가 나무라는 조건이 고려된다.

나무와 같은 제약조건 만족 문제의 이 특성은 부패방법에 의해 이용되는데, 이 방법은 문제를 나무로 배열된 이진 제약조건만 포함하는 동등한 것으로 변환한다.이러한 문제의 변수는 원래 문제의 변수 집합에 해당한다. 이러한 변수의 영역은 해당 원래 변수 집합에 범위가 포함된 원래 문제의 제약조건을 고려하여 얻는다. 이러한 새로운 문제의 제약조건은 포함된 변수의 동일성을 나타낸다.두 세트로 나누다

이와 같은 한 문제의 그래프가 나무라면 문제를 효율적으로 해결할 수 있다.한편, 두 가지 요인, 즉 변수 집합에 대한 제약 조건 집합의 결합 효과를 결정해야 하는 필요성과 주어진 제약 조건 그룹을 만족시키는 값의 모든 튜플을 저장해야 하는 필요성 때문에 이와 동등한 하나의 문제를 생성하는 것은 효율적이지 않을 수 있다.

트랙터블에 필요한 조건

보편적 기구에 기초한 제약 언어의 견인성에 필요한 조건이 입증되었다.보편적 기기는 새로운 관계를 투영하기 위해 처음에 정의한 특정한 제약 만족도 문제다.

범용 기기

제약조건 언어로 존재하지 않는 관계는 언어의 관계를 이용하여 제약에 의해 "시뮬레이션"될 수 있다.특히 일련의 제약조건을 배치하고 그 변수의 일부만 사용함으로써 새로운 관계를 만들 수 있다.다른 모든 제약조건이 이러한 변수만 사용하는 경우, 이 제약조건 집합은 이러한 변수를 특정 값만 가정하도록 강요하여 사실상 새로운 관계를 시뮬레이션한다.

모든 제약조건 만족 문제와 그 변수의 부분집합은 관계를 정의하는데, 이것은 다른 변수까지 확장되어 해결책을 형성할 수 있는 변수 값의 모든 튜플에 의해 구성된다.기술적으로, 이 관계는 고려된 변수에 대해 솔루션을 행으로 갖는 관계를 투영함으로써 얻어진다.

범용 가젯은 $도메인$에서 $k{\displaystyle }$ ${\$$displaystyle k}$ 요소의$$ 가능한 모든 열을 포함하는 관계를 투영함으로써 k ${\$$displaystyle k}$ -tuple을$$ 포함하는 모든 관계를 정의할 수 있다는 관찰에 기초한다.예를 들어, 다음 표는 그러한 투영을 보여준다.

a b c d e f g h d ------------------------ 1 1 1 1 1 1 1 0 0 0 0 -> 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0

왼쪽에 있는 테이블이 제약조건 만족도 문제의 해결책 집합인 경우 변수 $b{\displaystyle }$ ${\displaystyle b}$ 및 $d$ ${\displaystyle$ d$}$은(는) 오른쪽 테이블 값으로 제한된다$$.결과적으로 제약조건 만족도 문제는 제약조건 언어에 없을 수 있는 우측의 표와 관계가 있는 제약조건을 설정하는 데 사용될 수 있다.

결과적으로, 제약조건 만족도 문제가 해결책의 집합으로 왼쪽 표를 가지고 있는 경우, 적절한 변수 집합에 투영함으로써 모든 관계를 표현할 수 있다.이 표를 솔루션 집합으로 얻으려고 시도하는 방법은 필요한 솔루션에 의해 위반되지 않는 가능한 모든 제약조건을 배치하는 것이다.

예를 들어, 언어에 부울 분리를 나타내는 이진 관계(최소한 1을 포함하는 두 요소의 모든 튜플을 포함하는 관계)가 포함되어 있는 경우, 위의 표에 있는 값이${\displaystyle }$(${\displaystyle 1}$,${\displaystyle 1}$)${\displays$이기 때문에 이 $관계$는 ${\displaystyle a}$ 및 $b{\displaystyle }$ ${\displaysty$ b$}$에 제약조건으로 배치된다$.$$tyle (1,1$ ,${\displaystyle }$(${\displaystyle 1}$,${\displaystyle 1}$) 다시$${\$디스플레이 스타일 ($1,1$$$)},$${\displaystyle }$(${\displaystyle 1}$,${\displaystyle 0}$) ${\디스플레이$ 스타일 $(1,0$ 이 모든 값이 구속조건을 만족하기 때문에 제약조건이 배치된다.반면에 위의 표의 제한은 세 번째 행으로${\displaystyle }$(${\displaystyle 0}$, 0${\displaystyle }$) ${\displaystyle (0,0)$을 포함하며, 이 평가는 그러한 제약조건을 위반하기 때문에 $b{\displaystyle }$ ${\displaystyle b}$ $및$ d ${\displaystyd}$에 배치되지 않는다$.$

주문 $k{\displaystyle }$ ${\displaystyle k}$의 범용 가젯은 위의$$ 표를 얻기 위해 배치할 수 있는 모든 제약조건을 포함하는 제약조건 만족도 문제다.범용 가젯의 해결책은 이 표의 행을 포함하지만 다른 행을 포함할 수 있다.솔루션이 표의 행인 경우 모든 관계는 변수의 하위 집합에 투영하여 표시할 수 있다.그러나 해결책에 다른 행이 포함되더라도 일부 관계는 여전히 표현될 수 있다.보편적 기기의 속성은 동일한 언어에 기초한 임의의 제약조건 만족도 문제로부터 투영에 의해 표현될 수 있는 모든 관계를 투영으로 표현할 수 있다는 것이다.더 정확히 말하면, 순서 $k{\displaystyle }$ ${\displaystyle k}$의 범용 가젯은 제약조건 언어로 표현될 수 $있는{\displaystyle }$k {\$displaysty$k$$} 행의 모든 관계를 표현한다$$.

특정한 관계가 주어진다면, 언어에서의 그것의 표현가능성은 위의 표의 열이 그 관계를 형성하는 임의의 변수 목록(범용 가젯에 대한 "이상적인" 해결책)을 고려함으로써 확인할 수 있다.범용 기기의 솔루션이 그러한 변수 목록에 투영될 때 관계와 일치하는 경우에만 언어로 관계를 표시할 수 있다.즉, 범용 기기의 해답이 표와 같았던 것처럼 변수 '마치'를 선택하여 표현성을 확인한 다음, '실제' 해법의 제약이 실제로 관계와 동일한지 여부를 확인할 수 있다.위의 예에서 오른쪽 표의 관계 표현성은 범용 가젯의 솔루션이 $변수{\displaystyle }$ b ${\displaystyle b}$과 $d{\displaystyle }$ ${\displaystyle$ d$\}$로 제한되었을 때 이 표의 행이 정확한지 확인하여 확인할 수 있다.

범용 가젯에서 기능으로서의 솔루션

트랙터블에 필요한 조건은 보편적 기구에 의해 표현될 수 있다.그러한 기기의 해결책은 다음과 같이 표로 표시할 수 있다.

a b d e f g h ------------ 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 (정의에 의해 존재하는 경우) ---------------------------------------------------------------------------- 1 0 0 0 1 1 1 0 0 0 (다른 해결책도 가능) .... 

이 탁자는 두 부분으로 되어 있다.첫 번째 부분은 이 문제의 정의에 의해 존재하는 해결책을 포함하고, 두 번째 부분(비어 있을 수 있음)은 다른 모든 해결책을 포함하고 있다.표의 열은 도메인 값의 $가능$한 k ${\displaystyle k}$ -tuple과$$ 정의에 의해 연관되므로, 모든 솔루션은 $요소$의 k ${\displaystyle k}$ -tuple에서$$ 단일 요소에 이르는 함수로 볼 수 있다.

용액에 해당하는 함수는 위 표의 첫 번째 부분과 용액에서 계산할 수 있다.예를 들어, 표에 표시된 마지막 솔루션의 경우, 이 함수는 다음과 같이$$ 인수 $1{\displaystyle \mathrm{}}$,${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle$ 1,$0,1$}에 대해 결정할 수 있다. 첫째, 이 세 값은 표에 있는 행 "c"의 첫 번째 부분이며, 함수의 값은 같은 열의 솔루션 값, 즉 0이다.

트랙터블에 필요한 조건은 어떤 종류의 기능의 일부인 일부 질서의 보편적 기구에 대한 해결책의 존재다.그러나 이 결과는 아래에 정의된 축소된 언어에만 적용된다.

스쿼싱 기능 및 도메인 축소

스쿼싱 함수는 제약 언어의 도메인 크기를 줄이기 위해 사용되는 함수다.스퀴싱 함수는 도메인의 파티션과 파티션의 각 세트에 대한 대표 요소 측면에서 정의된다.스퀴싱 함수는 파티션에 있는 세트의 모든 요소를 그 세트의 대표 요소에 매핑한다.그러한 기능이 스퀴싱 함수가 되려면 언어의 관계 튜플의 모든 요소에 그 기능을 적용하는 것이 관계에서 또 다른 튜플을 생성하는 것도 필요하다.파티션은 적어도 1보다 큰 크기의 집합을 포함하는 것으로 가정한다.

정식으로, 적어도 하나 이상의 크기 집합을$$ 포함하는 $도메인{\displaystyle }$ D$${\$displaystyle D}$의 $파티션{\displaystyle {}_{}}$ D${\displaystyle {}_{}{1\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}${\$displaystyle D_{1},\ldots, D_{n}}$이(가) 주어지는 ${\displaystyle \mathrm{스쿼싱}}$ 함수는 함수${\displaystyle }s{\displaystyle }$ : ${\displaystyle D}$ → D${\displaystyle s:$$D\rightarrow D}$ such that ${\displaystyle s(x)=s(y)}$ for every ${\displaystyle x,y}$ in the same partition, and for every tuple ${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle \in R}$, it holds ${\displaystyle \langle s(x_{1}$$),\ldots ,s(x_{n})\rangele \in R}$.

제약조건 언어의 제약조건 문제에는 스쿼싱 기능이 있으므로 스쿼싱 기능을 통해 도메인을 줄일 수 있다.실제로 칸막이에 있는 세트의 모든 요소는 스퀴싱 기능을 적용한 결과로 대체될 수 있는데, 이 결과는 적어도 요소에 의해 충족된 모든 제약조건을 만족시킬 수 있다고 보장되기 때문이다.결과적으로, 모든 비대표적 요소들은 제약 언어에서 제거될 수 있다.

스쿼싱 기능이 없는 제약 언어를 감소된 언어라고 부른다. 동등하게, 스쿼싱 기능을 통한 모든 감소가 적용된 언어들이다.

트랙터블에 필요한 조건

이 구간은 확장이 필요하다.덧셈으로 도와줘도 된다.(2010년 2월)

범용 기구에 기초한 트랙터블에 대한 필수 조건은 감소된 언어에 대한 것이다.이러한 언어는 범용 기구가 위에서 지정한 방식으로 함수로 볼 때 상수 함수, 다수 함수, 공전 이항 함수, 부착 함수 또는 반투영인 해답을 가지고 있다면 추적할 수 있다.

참조

• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Vardi, Moshe Y. (2000). "Constraint Satisfaction and Database Theory: a Tutorial". PODS 2000. pp. 76–85.
• Bulatov, Andrei A. (2006). "A dichotomy theorem for constraint satisfaction problems on a 3-element set". Journal of the ACM. 53 (1): 66–120. doi:10.1145/1120582.1120584. S2CID 18220438.