비결정론적 제약 논리

이론 컴퓨터 과학에서, 비결정론적 제약 논리(non-determinatic restraint logic)는 특정한 제약에 따라 가중치 무방향 그래프의 가장자리에 방향이 주어지는 조합 체계이다.동일한 구속조건에 따라 단일 가장자리가 반전되는 단계를 통해 이 방향을 변경할 수 있습니다.구속 로직 문제와 그 변형은 PSPACE-complete로 증명되어 특정 에지를 반전시키고 다양한 게임과 퍼즐이 PSPACE-hard 또는 PSPACE-complete임을 보여주는 데 매우 유용한 움직임 시퀀스가 존재하는지 여부를 판단합니다.

이는 에지 방향 변경의 각 시퀀스를 취소할 수 있다는 점에서 가역 로직의 한 형태입니다.이 문제의 경도는 많은 게임과 퍼즐이 높은 게임 복잡성을 가지고 있다는 것을 증명하기 위해 사용되어 왔다.

제약 조건 그래프

구속 로직의 AND 게이트.노드의 최소 인도가 2이므로 두 개의 하단 에지가 들어가 있는 경우에만 상단 에지가 나올 수 있습니다.

제약 조건 ^[1]그래프의 예제입니다.

비결정론적 제약 로직의 가장 간단한 버전에서는 무방향 그래프의 각 가장자리는 1개 또는 2개의 가중치를 가집니다(무게는 가중치 1의 가장자리를 빨간색으로 그리고 가중치 2의 가장자리를 파란색으로 그려 그래픽으로 나타낼 수도 있습니다).그래프는 입방체 그래프여야 합니다.각 정점은 3개의 모서리에 입사하고, 또한 각 정점은 짝수의 빨간색 ^[2]모서리에 입사해야 합니다.

가장자리는 최소 두 개의 무게 단위가 각 정점을 향하도록 방향을 설정해야 합니다. 들어오는 파란색 가장자리 또는 들어오는 빨간색 가장자리 중 하나 이상이 있어야 합니다.방향은 이러한 ^[2]제약을 고려하여 단일 가장자리가 반전되는 단계에 따라 변경될 수 있습니다.

보다 일반적인 형태의 비결정적 제약 로직은 보다 다양한 에지 가중치, 정점당 더 많은 에지 및 각 정점이 가져야 하는 수신 가중치의 양에 대한 다른 임계값을 허용합니다.가장자리 무게 및 정점 임계값 시스템이 있는 그래프를 구속 그래프라고 합니다.가장자리 무게가 모두 1 또는 2이고, 정점은 들어오는 무게의 두 단위를 필요로 하며, 정점은 모두 짝수 수의 빨간색 모서리를 가진 세 개의 입사 모서리를 갖는 제한된 경우를 및/또는 제약 조건 ^[2]그래프라고 합니다.

이름 및/또는 제약 그래프의 이유는 두 가지 가능한 정점이 부울 로직의 AND 게이트 및 OR 게이트와 같은 방식으로 동작하기 때문입니다.빨간색 모서리가 두 개이고 파란색 모서리가 한 개 있는 정점은 파란색 모서리를 바깥쪽으로 가리키기 전에 빨간색 모서리가 모두 안쪽으로 향해야 한다는 점에서 AND 게이트와 같이 작동합니다.파란색 에지가 3개인 정점은 출력 에지를 ^[2]바깥쪽으로 가리키기 전에 적어도 1개의 입력 에지가 안쪽으로 향해야 한다는 점에서 두 개의 에지가 입력으로 지정되고 세 번째 에지가 출력으로 지정되는 OR 게이트와 같이 동작한다.

일반적으로 제약조건 논리 문제는 제약조건 그래프의 유효한 구성을 찾는 것에 대해 정의됩니다.구속조건 그래프는 두 가지 유형의 모서리를 가진 무방향 그래프입니다.

$무게$ 1의 빨간색 가장자리(\ $displaystyle$ 1)
$무게$ 2 $(\displaystyle$ 2

제약 그래프를 계산 모델로 사용하여 그래프 전체를 기계로 간주합니다.기계의 구성은 그래프와 모서리의 특정 방향으로 구성됩니다.유입 제약 조건을 만족하는 경우 구성을 유효하다고 합니다.각 정점은 $최소$ 2 $(\style$ 2 $2$ 의 들어오는 무게를 가져야 합니다.즉, 주어진 정점에 들어가는 에지의 무게 합계는 정점을 나가는 에지의 무게 합보다 $2$ 2(\ $displaystyle$ 2) 더 커야 합니다.

또한 구속 그래프에서 이동을 에지의 방향을 반전시키는 작업으로 정의하여 결과 구성이 여전히 유효합니다.

제약 로직 문제의 정식 정의

제약 조건 그래프, 시작 구성 및 종료 구성이 주어졌다고 가정합니다.이 문제는 시작 구성에서 종료 구성으로 이동하는 일련의 유효한 이동이 있는지 여부를 묻습니다. 이 문제는 3 정규 또는 최대 도수 3 그래프에 ^[3]대한 PSPACE-Complete입니다.QSAT 이후 감소된 내용은 다음과 같습니다.

변종

평면 비결정적 제약 논리

위의 문제는 구속 그래프가 평면인 경우에도 PSPACE-Complete입니다. 즉, 그래프는 두 모서리가 서로 교차하지 않도록 그릴 수 없습니다.이 감소는 Planel QSAT에서 비롯됩니다.

모서리 반전

이 문제는 앞의 특수한 경우입니다.제약 조건 그래프를 지정하면 일련의 유효한 이동으로 지정된 에지를 반전할 수 있는지 여부를 묻습니다.마지막 유효한 이동이 원하는 에지를 반전시키는 한 일련의 유효한 이동을 통해 이 작업을 수행할 수 있습니다.또한 이 문제는 3-정규 그래프 ^[3]또는 최대도 3 그래프에 대한 PSPACE-Complete로 입증되었습니다.

제약 조건 그래프 만족도

이 문제는 무방향 $그래프$ G(\ $style$ G $G$ 에서 유입 제약 조건을 충족하는 에지의 방향이 존재하는지 여부를 묻는 것으로, 이 문제는 NP-Complete로 ^[3]판명되었습니다.

어려운 문제

다음 문제, on 및/또는 구속조건 그래프와 그 방향은 PSPACE-complete입니다.^[2]

방향과 지정된 $가장자리$ e가 주어진 경우 주어진 방향에서 최종적으로 $가장자리$ e를 반전시키는 일련의 단계가 있는지 테스트합니다.
일련의 단계를 통해 한 방향을 다른 방향으로 변경할 수 있는지 테스트합니다.
지정된 방향의 두 $모서리$ $e$ 와 f가 주어진 경우, 전체 그래프에 대해 두 가지 방향이 있는지 테스트한다. 하나는 $e$ 에 지정된 방향을 가지며 다른 하나는 $f$ 에 지정된 방향을 가지며 일련의 단계를 통해 서로 변환할 수 있다.

이러한 문제가 어렵다는 증거는 및/또는 제약 조건 그래프의 논리적 해석에 기초한 정량화된 부울 공식으로부터의 감소를 포함한다.양자화기를 시뮬레이션하고 빨간색 가장자리에서 전달되는 신호를 파란색 가장자리에서 전달되는 신호로 변환하기 위해(또는 그 반대) 추가 가젯이 필요하며, 이 모든 것은 And-vertices와 ^[2]Or-vertices의 조합으로 달성할 수 있습니다.

이러한 문제는 평면 그래프를 형성하는 및/또는 제약 조건 그래프에서도 PSPACE-완전 상태로 유지됩니다.이것의 증거는 두 개의 독립된 신호가 서로 교차할 수 있도록 하는 교차 가젯의 구성을 포함한다.또한 이러한 문제의 경도를 유지하면서 추가적인 제한을 가할 수도 있습니다. 즉, 파란색 모서리가 3개인 각 정점은 빨간색 모서리가 있는 삼각형의 일부가 될 필요가 있습니다.이러한 정점은 보호됨 또는 보호됨이라고 불리며, 삼각형의 파란색 모서리 둘 다 안쪽으로 향할 수 없는 특성이 있습니다.이 제한으로 인해 다른 ^[2]문제에 대한 경도 감소에서 이러한 정점을 더 쉽게 시뮬레이션할 수 있습니다.또한 제약 그래프는 한정된 대역폭을 가져야 할 수 있으며, 이 그래프에 대한 문제는 PSPACE-complete인 ^[4]채로 남아 있습니다.

PSPACE 경도 증명

QSAT의 축소는 다음과 같습니다.QSAT 수식을 포함하기 위해서는 제약조건 그래프에 AND, OR, NOT, UNIVERSAL, EXISTEN셜 및 Converter (색상을 변경하기 위해) 가젯을 작성해야 합니다.아이디어는 다음과 같습니다.

AND 정점은 두 개의 빨간색 에지(입력)와 하나의 파란색 입사 에지(출력)를 갖는 정점입니다.
OR 정점은 세 개의 입사 파란색 에지(입력 2개, 출력 1개)가 있는 정점입니다.

다른 가젯도 이 방법으로 작성할 수 있습니다.전체 구성은 에릭 데메인의 ^[5]웹사이트에서 볼 수 있다.전체 구성은 대화형 방식으로 ^[6]설명됩니다.

적용들

비결정론적 제약 로직의 원래 적용은 러시 아워와 소코반과 같은 슬라이딩 블록 퍼즐의 PSPACE 완전성을 증명하기 위해 그것을 사용했다.이렇게 하려면 이러한 ^[2]퍼즐에서 모서리 및 모서리 방향, 정점 및 보호 또는 정점을 시뮬레이션하는 방법만 보여주면 됩니다.

비결정론적 제약 로직은 또한 경계 대역폭의 평면 그래프에서 독립 집합, 정점 커버 및 지배 집합을 포함한 고전적인 그래프 최적화 문제의 재구성 버전의 경도를 증명하기 위해 사용되었다.이러한 문제에서는 항상 나머지 정점이 ^[4]해답을 형성하는 속성을 유지하면서 한 번에 하나의 정점을 솔루션 집합으로 이동하거나 솔루션 집합 밖으로 이동함으로써 주어진 문제에 대한 해법을 다른 해로 변경해야 합니다.

재구성 3SAT

3-CNF 공식과 두 가지 만족스러운 할당이 주어진다면, 이 문제는 한 할당에서 다른 할당으로 우리를 데려가는 일련의 단계를 찾을 수 있는지 묻고, 각 단계에서 변수의 값을 뒤집을 수 있는지 여부를 묻습니다.이 문제는 비결정론적 제약 로직 ^[3]문제를 줄여 PSPACE-complete로 나타낼 수 있습니다.

슬라이딩 블록 퍼즐

이 문제는 블록의 초기 구성을 통해 슬라이딩 블록 퍼즐에서 원하는 구성에 도달할 수 있는지 여부를 묻습니다.이 문제는 직사각형이 ^[7]도미노인 경우에도 PSPACE-complete입니다.

러시 아워

이 문제는 초기 구성이 주어졌을 때 러시 아워 퍼즐의 승리 조건에 도달할 수 있는지 여부를 묻습니다.이 문제는 블록의 $1\times 2$ 가 1 $1\times 2$ × $1\times 2$ ^[3] $displaystyle 1\times$ 2)인 경우에도 PSPACE-complete입니다.

다이내믹 맵라벨

스태틱 맵을 지정하면 이 문제는 스무스한 다이내믹라벨이 존재하는지 여부를 묻습니다.이 문제도 PSPACE ^[8]완전합니다.

레퍼런스

^ "Constraint graphs". people.irisa.fr. Retrieved 2020-02-13.{{cite web}}: CS1 maint :url-status (링크)
^ ^a ^b ^c ^d ^e ^f ^g ^h 를 클릭합니다Hearn, Robert A.; Demaine, Erik D. (2005), "PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation", Theoretical Computer Science, 343 (1–2): 72–96, arXiv:cs/0205005, doi:10.1016/j.tcs.2005.05.008, MR 2168845, S2CID 656067.
^ ^a ^b ^c ^d ^e Demaine, Erik. "Non-Deterministic Constraint Logic" (PDF).
^ ^a ^b 반 데르 Zanden, 톰은 C.(2015년),"그래프의 Parameterized 복잡성 논리 제약 조건", 10일 국제 심포지엄 Parameterized에 엄밀한 계수, LIPIcs.라이프니츠 Int.Proc. 좀 알려 주세요., 43vol., 슐로스 Dagstuhl.Leibniz-Zent.., Wadern,를 대신하여 서명함. 282–293, arXiv:1509.02683, doi:10.4230/LIPIcs.IPEC.2015.282, 아이 에스비엔 9783939897927, MR3452428, S2CID 15959029에게 통보해야 한다.
^ Gurram, Neil. "Non Deterministic Constraint Logic" (PDF). Erik Demaine.
^ "Constraint graphs (an interactive website that explains constraint graphs and the reduction from QBF). By François Schwarzentruber". people.irisa.fr. Retrieved 2020-02-20.{{cite web}}: CS1 maint :url-status (링크)
^ Demaine, Erik D.; Hearn, Robert A. (2002-05-04). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs/0205005. Bibcode:2002cs........5005H. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Buchin, Kevin; Gerrits, Dirk H. P. (2013). Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (eds.). "Dynamic Point Labeling is Strongly PSPACE-Complete". Algorithms and Computation. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 8283: 262–272. doi:10.1007/978-3-642-45030-3_25. ISBN 9783642450303.

[1] "Constraint graphs". people.irisa.fr. Retrieved 2020-02-13.{{cite web}}: CS1 maint :url-status (링크)

[hd05-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h 를 클릭합니다Hearn, Robert A.; Demaine, Erik D. (2005), "PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation", Theoretical Computer Science, 343 (1–2): 72–96, arXiv:cs/0205005, doi:10.1016/j.tcs.2005.05.008, MR 2168845, S2CID 656067.

[:0-3] Demaine, Erik. "Non-Deterministic Constraint Logic" (PDF).

[vdz-4] 반 데르 Zanden, 톰은 C.(2015년),"그래프의 Parameterized 복잡성 논리 제약 조건", 10일 국제 심포지엄 Parameterized에 엄밀한 계수, LIPIcs.라이프니츠 Int.Proc. 좀 알려 주세요., 43vol., 슐로스 Dagstuhl.Leibniz-Zent.., Wadern,를 대신하여 서명함. 282–293, arXiv:1509.02683, doi:10.4230/LIPIcs.IPEC.2015.282, 아이 에스비엔 9783939897927, MR3452428, S2CID 15959029에게 통보해야 한다.

[5] Gurram, Neil. "Non Deterministic Constraint Logic" (PDF). Erik Demaine.

[6] "Constraint graphs (an interactive website that explains constraint graphs and the reduction from QBF). By François Schwarzentruber". people.irisa.fr. Retrieved 2020-02-20.{{cite web}}: CS1 maint :url-status (링크)

[7] Demaine, Erik D.; Hearn, Robert A. (2002-05-04). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs/0205005. Bibcode:2002cs........5005H. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[8] Buchin, Kevin; Gerrits, Dirk H. P. (2013). Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (eds.). "Dynamic Point Labeling is Strongly PSPACE-Complete". Algorithms and Computation. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 8283: 262–272. doi:10.1007/978-3-642-45030-3_25. ISBN 9783642450303.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search