The number of topological sorts in DAG, AND polytope centroid

Introduction

문제를 풀다 보면 “조건을 만족하는 해 $x$를 찾아라” 라는 문제는 쉽게 풀 수 있지만, “조건을 만족하는 해 $x$의 개수를 찾아라” 라는 문제가 유독 어려운 경우가 많습니다. 대표적으로 2-SAT은 다항 시간 안에 해를 찾을 수 있지만, 2-SAT의 조건을 모두 만족하는 해의 개수를 찾는 것은 매우 어렵다는 것이 알려져 있습니다. 비슷하게 이분그래프의 완전 매칭은 다항 시간 안에 찾을 수 있지만, 완전 매칭의 개수를 구하는 것은 permanent라는 계산하기 어려운 식과 동치가 됩니다.

오늘 다룰 주제는 Directed Acyclic Graph (DAG) 위에서의 위상정렬입니다. 역시 DAG의 위상정렬은 선형 시간 안에 찾을 수 있지만, 위상정렬의 개수를 찾는 것이 쉬운 일은 아닙니다. 오늘은 “개수를 세는 문제” 중에서 어려운 문제들을 모아둔 $\sharp P$-complete complexity class에 대해 다루고, DAG의 위상정렬 개수를 찾는 문제가 이에 속함을 보인 Brightwell & Winkler의 1991년 논문을 리뷰합니다.

다른 중요한 문제를 두고 이 문제를 다루는 이유는, 이를 바탕으로 지난 글에서 스쳐가듯 언급한 Polytope Centroid가 $\sharp P$-complete임을 설명할 수 있기 때문입니다. Polytope centroid를 빠르게 계산할 수 있을 때의 이점을 알려주는 Grunbaum’s theorem의 증명과 함께, Polytope centroid가 $\sharp P$-complete임을 위상정렬 문제로부터 유도합니다.

$\sharp P$-completeness

많은 complexity class는, “이 문제가 풀리지 않을 거다” 라는 강한 확신에서 시작합니다. 시작은 언제나 그렇듯 3SAT입니다. 3SAT의 satisfying assignment의 개수를 찾는 문제를 $\sharp3SAT$이라고 정의합시다.

Theorem (Toda, 1991). 모든 Polynomial Hierarchy의 문제 $A$에 대해, $A$는 $\sharp3SAT$ 으로 다항 시간 안에 reduce할 수 있다. 즉, $\sharp 3SAT$ 을 다항 시간 안에 해결할 수 있다면 $P = NP$가 성립한다.

Definition. (Polynomial Oracle Reduction) 두 함수 $f, g$에 대해, 임의의 input $x$에 대해 $g(x)$를 상수 시간에 계산할 수 있는 oracle $\mathcal{O} _ {g}$가 주어져 있다고 가정하자. 이 때 $f(x)$를 다항 시간 안에 계산할 수 있는 알고리즘 $M(\mathcal{O} _ {g}, x)$가 존재하면 $f \le _ {PO} g$ 라고 쓰고, $f$를 $g$로 polynomial-oracle reduce할 수 있다고 한다.

Definition ($\sharp P$-completeness)

$f \le _ {PO} \sharp 3SAT$이면, $f$를 $\sharp P$ 라고 정의한다.
임의의 $f \in \sharp P$에 대해 $f \le _ {PO} g$이면 $g$를 $\sharp P$-hard라고 한다.
$f\in \sharp P$가 $\sharp P$-hard라면 $f$를 $\sharp P$-complete이라고 한다.

보통 $\sharp P$의 정의는 다르게 하지만, 이 글에서는 이 정도로 충분합니다. 다음의 결과들이 알려져 있습니다.

(Valiant, 1979a). $\sharp 2SAT$ is $\sharp P$-complete.
(Valiant, 1979b). The number of perfect matchings in a bipartite graph is $\sharp P$-complete to compute.
The number of maximum cliques, maximum independent set, etc… is $\sharp P$-complete.

위 두 예시는 앞서 말했듯 decision problem이 $P$에 속함에도 counting problem이 어려운 경우입니다.

Counting Linear Extensions Is $\sharp P$-complete

Theorem (Brightwell 1991). Counting the number of topological sorts of a DAG is $\sharp P$-complete, even the DAG is of height $\le 5$.

여기서 DAG의 height란 최장 경로의 길이를 말합니다. Bril91은 같은 논문에서 height $\le 3$ 인 경우에도 $\sharp P$-complete이 됨을 설명했습니다. 의외로 height $\le 2$인 경우는 Bri91에서 추측이 나온 이후로 30년 가까이 지난 2020년에서야 Dittmer 등에 의해 $\sharp P$-complete임이 증명되었습니다.

$\sharp 3SAT$으로부터 reduce하기 위해서는, 임의의 $\sharp 3SAT$ instance를 위상정렬 개수 세기 oracle을 이용하여 다항 시간 안에 해결할 수 있다는 것을 보이면 됩니다. 해당 oracle을 앞으로는 $\mathrm{Topo}$라고 부르겠습니다.

임의의 3SAT instance $I$를 생각합시다. $n$개의 variable과 $m$개의 clause로 구성되어 있고, 각 variable $x$에 대응되는 literal $x, \neg x$, 그리고 각 clause는 literal 3개로 구성되어 있다고 가정합니다. $I$의 satisfying assignment의 개수를 $s(I)$라고 쓰겠습니다. 당연하지만 $s(I) \le 2^{n}$입니다.

Auxiliary POSET $G _ {I}$

이 때 $7m + n$ 개의 정점으로 구성된 DAG $G _ {I}$를 생각합니다. 앞으로 많이 나올 테니 $N = 7m + n$이라고 두겠습니다.

$V(G _ {I}) = \lbrace v _ {1}, \cdots, v _ {n}, c _ {1,001}, c _ {1, 010}, \cdots, c _ {1, 111}, \cdots, c _ {m, 001}, \cdots, c _ {m, 111} \rbrace$
- $v _ {1}, \cdots, v _ {n}$은 variable에 대응되는 vertex입니다.
- $c _ {j, k}$는 clause당 $2^{3} - 1 = 7$개씩의 정점을 할당한 것으로, $k$는 $\lbrace 1, 2, 3\rbrace$의 nonempty subset을 나타내는 비트마스크입니다.
$E(G _ {I})$: $j$번째 clause에 등장하는 variable을 $x, y, z$라고 하면, $v _ {x}$를 $c _ {j, \ast\ast1}$에, $v _ {y}$를 $c _ {j, \ast 1 \ast}$에, $v _ {z}$를 $c _ {j, 1\ast \ast}$에 연결합니다. 따라서 총 $12m$개의 간선이 존재하게 됩니다.

이 때, $G _ {I}$의 위상 정렬 개수를 $L _ {I}= \mathrm{Topo}(G _ {I})$라고 합시다. 당연히 $L _ {I} \le M!$이 성립합니다. 이 $L _ {I}$는 답과 직결되어 있다기보다, 답과 같이 곱해져 나오는 비례상수입니다. 앞으로 일어날 일은

적당한 소수 $p$에 대해, oracle로부터 $L _ {I} \cdot C(n, m, p) \cdot s(I) \pmod{p}$ 를 구할 수 있다.
$C(n, m, p)$는 $p$의 배수가 아님이 보장되어 있는데, $L _ {I}$는 아닐 수도 있다.
그러니 $L _ {I}$를 나누지 않는 소수 $p$에 대해서만 1. 의 과정을 수행한 뒤, $L _ {I} C(n, m, p)$의 역수를 곱하면 된다.
그런 $p$가 충분히 많기만 하다면, 즉 모두 곱해 $2^{n}$만 넘는다면 중국인의 나머지 정리를 통해 $s(I)$를 복구할 수 있다.

이를 뒷받침해 주기 위한 정리가 바로 아래 정리입니다.

Lemma. $n > 4$에 대해, $n$ 이상 $n^{2}$ 이하의 소수를 모두 곱하면 적어도 $n! \cdot 2^{n}$ 이상이다.

증명은 해석적 정수론을 열심히 쓰면 됩니다. 이제 $M$ 이상 $M^{2}$ 이하의 소수들을 모두 곱한 값은 최소 $M! 2^{M}$인데, 이 중 $L _ {I}$를 나누지 않는 값만 곱하면, $L _ {I} \le M!$이므로 역시 $2^{M}$ 이상입니다. 따라서 다항 시간 안에 조건을 만족하는 소수들의 목록을 구할 수 있습니다. 이제 소수 $p$를 고정하고, 1번의 과정을 구현해봅시다.

Augmented Auxiliary POSET

이제 $n, m$, 그리고 적당히 고른 소수 $p$가 주어져 있습니다. 아래와 같은 DAG $P$를 설계합니다. 편의상 POSET의 용어를 비슷하게 사용하여, 정점 $x$와 $y$ 사이에 간선이 있다는 것을 $x \le y$와 같이 표기하고, 집합 $U, V$에 대해서도 $U \le V$이면 $\forall u \in U, v \in V\; u \le v$와 같이 유연하게 해석합니다.

세심한 construction이니만큼 모든 조건을 주의해서 읽어주세요.

$V(P)$의 멤버는 $B _ {0}, B _ {1}, \cdots, B _ {n}, \lbrace a \rbrace, M _ {0}, M _ {1}, \cdots, M _ {m}, \lbrace b \rbrace, \lbrace v _ {1}, \neg v _ {1}, \cdots, \neg v _ {n} \rbrace, \lbrace c _ {1,000}, \cdots, c _ {1, 111}, \cdots, c _ {m, 000}, c _ {m, 111}\rbrace$의 합집합으로 이루어진 거대한 집합입니다.
$B _ {i}$는 각각 크기 $p-1$의 antichain으로, $B _ {i} \le \lbrace a, v _ {i}, \neg v _ {i} \rbrace$가 성립합니다. $v _ {0}$가 존재하지 않으므로 $B _ {0}$는 $a$로만 간선을 뻗고 있음에 주의하세요.
- 이들은 $P$에서 “1층”을 담당하는 정점들입니다.
- $a$는 1층의 모든 정점들 “위에” 있고, 2층의 모든 정점들 “아래”에 있습니다. 위-아래는 $\le$에 의해 결정되는 자연스러운 순서로 해석합니다.
$M _ {i}$는 각각 크기 $p-1$의 antichain으로, $a \le B _ {i} \le \lbrace b, c _ {i, \ast}\rbrace$가 성립합니다. $c _ {0, \ast}$는 역시 존재하지 않으므로 마찬가지로 $a \le B _ {0} \le b$가 됩니다.
- 이들은 $P$에서 “2층”을 담당하는 정점입니다.
- $b$는 2층의 모든 정점들 위에 있고, 3층의 모든 정점들 아래 있습니다.
$v _ {1}, \cdots, v _ {n}, \neg v _ {1}, \cdots, \neg v _ {n}$은 각각의 literal에 대응됩니다.
$c _ {j, k}$는 clause들에 대응되는데, $k$는 clause의 variable을 어떻게 사용할지에 대한 비트마스크입니다. 이에 따라 자연스럽게 가령 $j$번째 clause가 $x \vee \neg y \vee z$라고 한다면, $v _ {x}, v _ {y}, v _ {z} \le c _ {j, 000}$이고, $v _ {x}, \neg v _ {y}, v _ {z} \le c _ {j, 010}$이 되는 식입니다.
- $v _ {i}, c _ {j}$만 떼어내서 비교하면 예전에 만들었던 $G _ {I}$와 비슷한 것 같지만 아직은 살짝 다릅니다.
이 때, 특별히 각 clause를 이루는 literal과 정확히 같은 비트마스크에만 $b$에서 하나씩 간선을 그어줍니다. 위의 예시에서 $b \le c _ {j, 010}$이 됩니다.
- 이 정점들은 $P$에서 꼭대기인 “3층”을 담당합니다.

이것들이 $P$에 존재하는 정점과 간선의 전부입니다. $p \le M^{2}$이므로, 정점의 개수를 다 합쳐보면 $M^{3}$ 이하임을 알 수 있습니다. 이제 $\mathrm{Topo}(P) \mod p$를 계산해봅시다!

Contributing topological orderings

Topological sorting은 결국 DAG를 POSET으로 쓰면 total order를 준다는 것과 완전히 같은 이야기입니다. 이 때 $B _ {i} \le a \le M _ {i} \le b$ 라는 큰 틀의 순서는 결정되어 있으므로, 남은 literal 정점들과 clause 정점들의 위치를 결정하면 좋을 것 같습니다. 이 때 literal 정점들과 clause 정점들을 1층, 2층, 그리고 3층으로 분할합시다. 이 중 하나인 $F = (F _ {1}, F _ {2}, F _ {3})$에 대해 $F _ {1} \le a \le F _ {2} \le b \le F _ {3}$이라는 간선들을 추가한 새로운 그래프 $P \oplus F$를 생각합시다. 당연히 $P \oplus F$인 $F$들만 볼거고, 이러한 $F$들의 모임을 $\Phi$라고 쓰면 아래와 같이 쓸 수 있습니다.

$\displaystyle \mathrm{Topo}(P) = \sum _ {F \in \Phi} \mathrm{Topo}(P \oplus F)$

이제 임의의 $F$에 대해 $x(\neq a, b) \in P \oplus F$는 $x < a, a < x < b, x > b$ 셋 중 하나만 만족합니다. 각각을 만족하는 정점들만 취해 만든 induced sub-DAG를 $\alpha(F), \beta(F), \gamma(F)$라고 씁시다. $P \oplus F$의 topological order는 세 sub-DAG의 topological order에 의해 독립적으로 결정됩니다.

$\displaystyle \mathrm{Topo}(P) = \sum _ {F \in \Phi} \mathrm{Topo}(\alpha(F))\mathrm{Topo}(\beta(F))\mathrm{Topo}(\gamma(F))$

우리는 $\mod p$만 원하기 때문에, $\mathrm{Topo}(\alpha(F)), \mathrm{Topo}(\beta(F)) \not\equiv 0\pmod{p}$인 $F$에 대해서만 볼 겁니다. 이러한 $F$들의 모임을 $\Phi _ {1}$이라고 둡시다. 1층과 2층에 들어간 원소들의 꼴에서 짐작할 수 있듯, 이 조건을 만족하는 $F$의 형태는 굉장히 제한적입니다. 위 식을 정제해서 쓰면,

$\displaystyle \mathrm{Topo}(P) \equiv \sum _ {F \in \Phi _ {1}} \mathrm{Topo}(\alpha(F))\mathrm{Topo}(\beta(F))\mathrm{Topo}(\gamma(F)) \pmod{p}$ 와 같습니다. $\Phi$가 $\Phi _ {1}$으로 바뀌었으니 등식도 modulo $p$ 합동식으로 바뀌게 됩니다.

“1층”

$\alpha(F)$를 생각합시다. 우선 여기에 clause vertex $c _ {j, k}$는 $b \le c _ {j, k}$이므로 들어올 수 없습니다. 따라서 몇 개의 literal vertex만 들어올 수 있습니다. 그런데 여기에는 몇 개의 isolated vertex, 즉 degree $0$인 vertex들이 있습니다. 이들의 개수를 $r$개라고 두면, $B _ {0}$의 원소들은 전부 isolated이니 $(\because a \notin \alpha(F))$ $r \ge p-1$입니다. $k := \lvert V(\alpha(F)) \rvert$라고 두면, isolated vertex들은 따로 빼 두었다가 마지막에 topological order에 집어넣어도 전혀 상관이 없으니, $\mathrm{Topo}(\alpha(F))$는 최소한 $(k-r+1)(k-r+2) \cdots k$의 배수가 됩니다.

이 때 만약 $r \ge p$라면 위 식이 $p$의 배수가 되므로, $r = p-1$일 조건을 생각해 봅시다.

모든 $1 \le i \le n$에 대해, $v _ {i}, \neg{v _ i}$ 중 하나는 $\alpha(F)$에 속해야 한다. 그렇지 않으면 $B _ {i}$는 isolated.

$v _ {i}, \neg v _ {i}$가 모두 들어올 수 있을까요?

위 식이 $p$의 배수가 되지 않으려면 $k \equiv -1 \pmod{p}$가 성립해야 합니다. literal vertex들은 $m$개 이상 $2m$개 이하로 들어와야 하므로, $(m+1)(p-1) + m \le k \le (m+1)(p-1) + 2m$입니다. 이 때 $p > m$이므로, 조건을 만족하는 $k = (m+1)(p-1) + m$뿐입니다. 따라서 $v _ {i}, \neg v _ {i}$ 중 정확히 하나만 $\alpha(F)$에 속해야 합니다.

위 조건이 모두 만족되는 경우, $\mathrm{Topo}(\alpha(F))$는 $k! / p^{m} = (mp + p -1)! / p^{m}$이 됩니다. 이것이 $p$의 배수가 아님은 자명합니다. 가능한 $k!$개의 ordering 중, $B _ {i} \le v _ {i}$ (혹은 $\neg v _ {i}$, 둘 중 $\alpha(F)$에 속하는 것) 를 만족하는 ordering의 비율은 $1 / p$이고, 사건 $B _ {i} \le v _ {i}$는 각 $i = 1, \cdots, m$에 대해 독립이기 때문입니다.

“2층”

2층을 구성하는 $\beta(F)$에는 몇 개의 literal vertex, clause vertex 들이 모두 들어올 수 있습니다.

비슷하게, isolated vertex의 개수는 $p-1$개여야 합니다. 정확히 $M _ {0}$의 크기와 같습니다. 그런데 literal vertex들은 $\beta(F)$에 들어오면 isolated가 되므로, $\beta(F)$에는 clause vertex들만 존재해야 함을 알 수 있습니다. 마찬가지로 $p > n$임을 염두하며 1층과 동일한 argument를 펴면, $1 \le j \le n$에 대해 8개의 $c _ {j, \ast}$ 중 정확히 하나만 $\beta(F)$에 속해야 합니다.

비슷하게, 위 조건을 모두 만족하는 경우 $\mathrm{Topo}(\beta(F)) = (np + p-1)! / p^{n}$이 됩니다.

“3층”

3층을 구성하는 $\gamma(F)$에는 이제 각 $j$마다 7개의 $c _ {j, \ast}$와, $n$개의 literal vertex들이 위치합니다. 특히 마지막 조건 때문에 literal의 형태를 보존하는 비트마스크 $b _ {j}$에 대해 $c _ {j, b _ {j}}$는 무조건 $3$층에 위치하게 됩니다. 이 때, 다음의 놀라운 성질이 성립합니다.

Proposition. $u _ {1}, \cdots, u _ {n}$을 3층에 속하는 literal vertex라고 하자. $u _ {i} \in \lbrace v _ {i}, \neg v _ {i} \rbrace$이다. 이 때 $\phi(u) := (u _ {i} == v _ {i})$로 주어지는 assignment는 satisfying assignment이다. 나아가, $F \mapsto u \mapsto \phi(u)$는 satisfying assignment와 $\Phi _ {1}$ 사이의 bijection이다.

Corollary. Proposition으로부터, 다음이 성립한다.

$\gamma(F)$는 $G _ {I}$와 isomorphic. 따라서 $\mathrm{Topo}(\gamma(F)) = L _ {I}$.
따라서, $\displaystyle \mathrm{Topo}(P) \equiv \sum _ {F \in \Phi _ {1}} \mathrm{Topo}(\alpha(F))\mathrm{Topo}(\beta(F))\mathrm{Topo}(\gamma(F)) \equiv \frac{(mp+p-1)!(np+p-1)!L _ {I}}{p^{m+n}} \cdot \lvert \Phi _ {1} \rvert \equiv C(n, m, p) \cdot s(I) \pmod{p}$.
$C(n, m, p)$는 당연히 $p$의 배수가 아니므로, 이로부터 $s(I)\bmod p$를 계산할 수 있다.

Proposition의 증명은 다음과 같습니다. 가령 $i$번째 clause가 $x \vee y \vee \neg z$라고 하면, 이 clause를 “falsify”하는 $\neg v _ {x}, \neg v _ {y}, v _ {z}$가 모두 3층 $\gamma(F)$에 들어올 수는 없습니다. $c _ {i, 001}$을 제외한 $7$개의 clause vertex가 모두 저 세 literal보다 위에 있기 때문에, $b \le c _ {i, 001} \implies c _ {i, 001} \in \gamma(F)$와 모순되기 때문입니다. 따라서, 모든 clause vertex에 대해 조건을 만족한다면 $\gamma(F)$의 literal vertex만 모아서 satisfying solution을 만들 수 있게 됩니다. 반대로 satisfying solution이 주어지면 이로부터 $\gamma(F)$에 들어갈 literal vertex가 정해지고, 이로부터 2층에 내려갈 clause, 1층에 내려갈 literal까지 유일하게 결정됩니다. $\square$

Corollary의 1번 정도만 비자명하게 되는데, 결국 각각의 literal을 variable로 보면 금방 $G _ {I}$와의 isomorphism을 찾을 수 있습니다. 이로부터 $\sharp 3SAT$을 Topological sort counting으로 reduce하였으므로, Topological Sort Counting은 $\sharp P$-complete이 됩니다. $\square$

Polytope centroid

이제 이 글의 두 번째 주제인 polytope의 무게 중심에 대해 이야기해봅시다. 제 지난 글에서도 다루었지만, polytope에서 centroid를 알 수 있다는 것은 상당한 이점이 있습니다. 특히 Linear Programming의 경우 half-plane intersection으로 주어지는 polytope의 한 점을 찾는 문제로 변환할 수 있는데, 무게중심을 지나는 아무 half-plane으로만 잘라도 polytope의 부피가 $(1 - \frac{1}{e})$배 이상 줄어듭니다. 따라서 polytope $P$가 half-plane intersection $H _ {1} \cap H _ {2} \cap \cdots \cap H _ {n}$으로 주어지면, $P$의 원소를 아무거나 하나 찾는 문제를 다음과 같이 쉽게 해결할 수 있습니다.

$P$를 포함하는 적당한 polytope $Q$를 잡는다. (문제에 따라 hypercube, ellipsoid 등)
$Q$의 centroid $c$를 계산한다. $c \in P$이거나 $c \notin H _ {j}$인 $j$가 존재한다. $c \in P$면 끝.
$c$를 지나고, $H _ {j}$를 결정하는 hyperplane과 평행한 hypeplane으로 $Q$를 자른다. 부피가 $(1 - \frac{1}{e})$ 이하로 줄어들고, 여전히 $P \subseteq Q$이다.
이를 계속 반복하다보면, $\mathrm{vol}(Q) < \mathrm{vol}(P)$가 될 수 없으므로 반드시 2번 step에서 $c \in P$가 성립한다.

따라서 $V = \mathrm{vol}(Q) / \mathrm{vol}(P)$라고 하면 대략 $\mathcal{O}(\log V)$번의 iteration만으로 문제를 해결할 수 있습니다. 이는 알려진 ellipsoid method 등에 비해 훨씬 빠른데, 이를 구현하지 못하는 이유가 centroid를 계산하기 어렵기 때문입니다.

우선 3번의 내용을 보장하는 핵심 정리인 Grunbaum’s theorem에 대해서 알아봅시다.

Theorem (Grunbaum, 1960) 원점이 무게중심인 $\mathbb{R}^{d}$의 compact convex body $K$를 hyperplane $H = \lbrace (x _ {1}, \cdots, x _ {n}) \mid x _ {1} \ge 0 \rbrace$ 을 기준으로 자른다고 하자. 이 때 $\frac{\mathrm{vol}(K \cap H)}{\mathrm{vol}(K)} \ge \left( \frac{d}{d+1} \right)^{d} \ge e^{-1}$.

$K$를 rotate하면 임의의 hyperplane과 동일한 것을 알 수 있습니다. 증명은 3단계로 크게 나뉘는데, 간단히 스케치만 하고 넘어가기로 합니다. 자세한 증명은 reference를 참고하시면 됩니다.

$K$가 cone인 경우에는 쉽습니다. 즉, hyperplane $x _ {1} = -c$에 완전히 포함되는 $d-1$차원 ball과 그 바깥의 한 점의 minkowski sum으로 주어진 경우에, 단순히 미적분학 문제가 됩니다. $d = 2$인 예시로는 삼각형, $d = 3$의 예시로는 원뿔이 있습니다. 일례로 삼각형을 무게중심을 지나는 (변에 평행한) 직선으로 자르면 두 조각의 넓이비는 $4 : 5$가 되는데, $\frac{4}{9} = \left(\frac{2}{2+1}\right)^{2}$입니다.
$K$가 cone이 아닌 경우, volume ratio를 보존하며 spherically symmetric한 다른 convex body로 바꿀 수 있습니다. 이 과정에서 Brunn-Minkowski inequality라는 비자명한 부등식이 사용되는데, 엄청 크리티컬한 건 아니고 새로 만든 body가 convex하다는 걸 보이는 데 사용합니다.
이제 $K$가 spherically symmetric인데 cone이 아닌 경우가 남는데, 비슷하게 volume ratio를 보존하는 cone을 $x _ {1} \ge 0$쪽에 끝점이 오도록 만들어주면 무게중심이 $x _ {1} > 0$ 쪽으로 $0$ 이상 이동한다는 걸 계산할 수 있습니다. 이는 곧 원래 $K \cap H$의 mass가 전체의 $\left(\frac{d}{d+1}\right)^{d}$ 이상이었다는 것입니다.

Computing centroid is hard

Computing volume of order polytope is hard

Polytope의 한 종류로, 다음 polytope들의 intersecion으로 생기는 $d$차원의 polytope “order polytope”을 생각합니다.

$H _ {i, j} := \lbrace x _ {1}, \cdots, x _ {d} \in [0, 1]^{d} \mid x _ {i} \le x _ {j} \rbrace$

이 때, 어떤 non-degenerate order polytope이 주어지면 그에 따라 유일하게 DAG가 하나 주어집니다. $P \subseteq H _ {i, j}$이면 $i \to j$ 간선을 긋는 식입니다. polytope $P$에서 유도되는 DAG를 $D(P)$라고 두면,

Theorem. $\mathrm{vol}(P) = \frac{1}{d!}\mathrm{Topo}(D(P))$. 따라서, $\mathrm{vol}(P)$는 $\sharp P$-complete.

Proof. $[0, 1]^{d}$는 임의의 길이 $d$ 순열 $\pi$마다 하나씩 대응되는, 총 $d!$ 개의 order simplex $H _ {\pi(1), \pi(2)} \cap \cdots \cap H _ {\pi(d-1), \pi(d)}$로 분할할 수 있고, 각각은 order polytope 안에 완전히 포함되거나 서로소이다. order polytope 간의 포함관계는 DAG 상에서 역포함관계이므로, $P$에 포함되는 order simplex의 개수는 곧 $D(P)$에 줄 수 있는 total order의 개수가 된다. $\square$

전혀 무관해보이던 두 주제가 “부피”라는 면에서 공통점을 갖는 순간입니다. 이제 이를 바탕으로 centroid의 $\sharp P$-hardness를 증명합니다.

Theorem. $P$가 order polytope일 때조차, $P$의 centroid는 $\sharp P$-hard to compute.

Proof. Convex body $K$를 $K _ {1} \sqcup K _ {2}$로 분할하면, centroid $c(K)$는 $\mathrm{vol}(K)c(K) = \mathrm{vol}(K _ {1})c(K _ {1}) + \mathrm{vol}(K _ {2})c(K _ {2})$ 를 만족합니다. 이는 $K$의 mass를 centroid 한 점에 뭉쳐 생각할 수 있다고 보면 자명합니다. 이제 이를 바탕으로, centroid oracle이 주어지면 다항 시간 내로 order polytope의 부피를 계산할 수 있다는 것을 보이면 됩니다.

$P = H _ {a _ {1}, b _ {1}} \cap \cdots \cap H _ {a _ {n}, b _ {n}}$이라고 두면, 맨 처음에 $Q _ {0} = [0, 1]^{d}$를 두고 아래와 같이 volume을 계산해 나갑니다.

$Q _ {i} = Q _ {i-1} \cap H _ {a _ {i}, b _ {i}}$, $R _ {i} := Q _ {i-1} \backslash H _ {a _ i, b _ i} = Q _ {i-1} \cap H _ {b _ i, a _ i}$
$\mathrm{vol}(R _ {i}) / \mathrm{vol}(Q _ {i}) = \mathrm{vol}(Q _ {i-1}) / \mathrm{vol}(Q _ {i}) - 1 = \lVert c(R _ {i}) - c(Q _ {i-1}) \rVert / \lVert c(Q _ {i}) - c(Q _ {i-1}) \rVert$

$Q _ {n} = P$이므로, 위에서 구한 volume ratio를 모두 곱하면 $\mathrm{vol}(P)$를 계산할 수 있습니다. 이 때 $Q _ {i}, R _ {i}$는 모두 order polytope이므로, 위의 theorem에 따라 volume은 모두 $O(d \log d)$ 비트의 유리수로 표현할 수 있습니다. 나아가 centroid의 좌표 또한 (order simplex 들의 centroid 좌표) 여러 개를 선형 결합하여 만들 수 있으므로 다항 비트의 유리수로 표현할 수 있고, 중간 관계식인 volume ratio또한 다항 시간 안에 계산이 가능한 양입니다. $\square$

Conclusion

원래 이 글의 기획 의도는 volume, centroid 계산의 hardness를 증명하는 것이었습니다. 하지만 이를 조사하는 과정에서 topological sort counting이라는 문제의 hardness를 접할 기회가 생겼고, polytope과 POSET간의 흥미로운 bijection 또한 얻을 수 있었습니다. Topological sort 뿐만 아니라, $\sharp P$-completeness를 보이는 reduction은 solution의 경우의 수를 어떤 형태로든 보존해야 하기 때문에 상당히 섬세한 tool들이 많이 사용된다는 것을 다시 한 번 느낍니다.

References

Dem22: E. D. Demaine et al. Computational Intractability: A Guide to Algorithmic Lower Bounds (Draft, 2022-10-22 ver) Chap 12
Tod91: Toda, Seinosuke. “PP is as hard as the polynomial-time hierarchy.” SIAM Journal on Computing 20.5 (1991): 865-877.
Bri91: Brightwell, Graham, and Peter Winkler. “Counting linear extensions is# P-complete.” Proceedings of the twenty-third annual ACM symposium on Theory of computing. 1991.
- 오늘의 메인 논문입니다.
Ditt18: Dittmer, Samuel, and Igor Pak. “Counting linear extensions of restricted posets.” arXiv preprint arXiv:1802.06312 (2018).
- height 2 poset의 linear extension count에 관한 hardness입니다.
Rad07: Rademacher, Luis A. “Approximating the centroid is hard.” Proceedings of the twenty-third annual symposium on Computational geometry. 2007.
Fur86: Furedi, Z., and I. Barany. “Computing the volume is difficult.” Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing. 1986.