♯01-パーマネントのP完全性

有用な特性${\displaystyle G_{\phi }}$そのサイクルカバーは変数割り当てに対応している${\displaystyle \phi }$自転車カバー用${\displaystyle Z}$の${\displaystyle G_{\phi }}$次のように言える${\displaystyle Z}$変数に値を割り当てる${\displaystyle \phi }$念のため${\displaystyle Z}$すべての外部エッジが含まれています${\displaystyle x_{i}}$の T サイクルと外部エッジのいずれも${\displaystyle x_{i}}$すべての変数に対するFサイクル${\displaystyle x_{i}}$代入によって真となること、そしてすべての変数についてその逆もまた同様である。${\displaystyle x_{i}}$割り当てが偽である。${\displaystyle Z}$割り当てを誘発する必要はありません${\displaystyle \phi }$、そうするものは正確に 1 つの割り当てを誘導し、誘導される同じ割り当ては外部エッジのみに依存します。${\displaystyle Z}$。 用語${\displaystyle Z}$この段階では、外側の縁についてのみ言及しているため、不完全なサイクルカバーとみなされます。${\displaystyle M}$以下のセクションでは、${\displaystyle M}$-各サイクルカバーに対応するサイクルカバーのセットがあることを示すための完了${\displaystyle M}$必要な特性を備えているもの。

カバーの種類${\displaystyle Z}$代入を誘発しないのは、節の構成要素内で「ジャンプ」するサイクルを持つものです。つまり、すべての${\displaystyle C_{j}}$少なくとも1つ${\displaystyle C_{j}}$の入力エッジは${\displaystyle Z}$節コンポーネントのすべての出力エッジは${\displaystyle Z}$対応する入力エッジが${\displaystyle Z}$、 それから${\displaystyle Z}$各節の構成要素に関して適切であり、${\displaystyle Z}$満足のいく課題を生み出すでしょう${\displaystyle \phi }$これは、適切なカバーが${\displaystyle Z}$すべての変数の完全なTサイクルまたは完全なFサイクルのいずれかを含む${\displaystyle x_{i}}$で${\displaystyle \phi }$また、各節コンポーネントに出入りするエッジもそれぞれ含まれます。したがって、これらのカバーは、各節コンポーネントに真または偽（両方ではない）のいずれかを割り当てます。${\displaystyle x_{i}}$そして、各条項が満たされていることを確認する。さらに、そのようなすべてのサイクルカバーの集合${\displaystyle Z}$体重がある${\displaystyle 12^{m}}$、その他${\displaystyle Z}$重さがある${\displaystyle 0}$その理由は、節の構成要素の構造によって異なり、以下に概説する。

節の構成要素の関連特性を理解する${\displaystyle C_{j}}$そのためには、M-完成の概念が必要となる。サイクルカバー${\displaystyle Z}$外部エッジが特定の特性を満たす場合に限り、満足のいく割り当てを誘導します。${\displaystyle G_{\phi }}$外部のエッジのみを考慮すると、部分集合は${\displaystyle M}$。 させて${\displaystyle M}$外部エッジの集合。内部エッジの集合${\displaystyle L}$は${\displaystyle M}$念のため完了${\displaystyle M\cup L}$自転車カバーは${\displaystyle G_{\phi }}$さらに、すべての集合を次のように表す。${\displaystyle M}$-完了${\displaystyle L^{M}}$そして、結果として得られるすべてのサイクルカバーのセットは${\displaystyle G_{\phi }}$による${\displaystyle Z^{M}}$。

建設を思い出してください${\displaystyle G_{\phi }}$各外部エッジの重みが 1 であったため、${\displaystyle Z^{M}}$サイクルは、あらゆる結果から生じる${\displaystyle M}$は、関係する内部エッジのみに依存します。ここで、節の構成要素の構成が、可能なものの合計が${\displaystyle M}$-各節コンポーネント内の内部エッジの重みの完了、${\displaystyle M}$節の構成要素に対して適切な場合は 12 です。それ以外の場合は、内部エッジの重みは 0 です。${\displaystyle m}$節の構成要素、および内部エッジのセットの選択、${\displaystyle L}$各節コンポーネント内では、他の節コンポーネント内の内部エッジのセットの選択とは独立しているため、すべてを掛け合わせて重みを取得できます。${\displaystyle Z^{M}}$なので、それぞれの重量は${\displaystyle Z^{M}}$、 どこ${\displaystyle M}$満足のいく課題を誘発し、${\displaystyle 12^{m}}$さらに、${\displaystyle M}$満足のいく課題を引き出さない、${\displaystyle M}$一部に関しては適切ではない${\displaystyle C_{j}}$内部エッジの重みの積は${\displaystyle Z^{M}}$になるだろう${\displaystyle 0}$。

節コンポーネントは、重み付き有向グラフであり、7つのノードを持ち、エッジには重みが付けられ、ノードは上記の特性が得られるように配置されています。これは、Ben-DorとHalevi（1993）の付録Aに示されています。ここで、内部エッジの重みは、集合から取得されることに注意してください。${\displaystyle \{-1,0,1,2,3\}}$;すべての辺に0～1の重みがあるわけではありません。

最後に、特定の満足割り当てを誘導するサイクルカバーのすべてのセットの重みの合計は${\displaystyle 12^{m}}$、そして他のすべてのサイクルカバーの重みの合計は 0 であり、${\displaystyle \operatorname {Perm} (G_{\phi })=12^{m}\cdot (\#\phi )}$次のセクションでは計算を削減します。${\displaystyle \operatorname {Perm} (G_{\phi })}$01マトリックスのパーマネントへ。

モジュラー演算を使用して、整数行列を変換します。${\displaystyle A}$同等の非負行列に変換する${\displaystyle A'}$そのため、${\displaystyle A}$は、パーマネントから簡単に計算できます。${\displaystyle A'}$、 次のように：

させて${\displaystyle A}$になる${\displaystyle n\times n}$整数行列で、どの要素もそれより大きい値を持たない${\displaystyle \mu }$。

• 計算する${\displaystyle Q=2\cdot n!\cdot \mu ^{n}+1}$選択${\displaystyle Q}$それは、${\displaystyle |\operatorname {Perm} (A)|\leq n!\cdot \mu ^{n}}$
• 計算する${\displaystyle A'=A\,{\bmod {\,}}Q}$
• 計算する${\displaystyle P=\operatorname {Perm} (A'){\bmod {Q}}}$
• もし${\displaystyle P<Q/2}$その場合、Perm( A ) = Pとなる。それ以外の場合は、${\displaystyle \operatorname {Perm} (A)=P-Q}$

変革${\displaystyle A}$の中へ${\displaystyle A'}$は多項式である${\displaystyle n}$そして${\displaystyle \log(\mu )}$表現に必要なビット数${\displaystyle Q}$は多項式である${\displaystyle n}$そして${\displaystyle \log(\mu )}$

変換の例と、それが機能する理由を以下に示します。

${\displaystyle A={\begin{bmatrix}2&-2\\-2&1\end{bmatrix}}}$

${\displaystyle \operatorname {Perm} (A)=2\cdot 1+(-2)\cdot (-2)=6.}$

ここ、${\displaystyle n=2}$、${\displaystyle \mu =2}$、 そして${\displaystyle \mu ^{n}=4}$、 それで${\displaystyle Q=17}$。 したがって

${\displaystyle A'=A{\bmod {1}}7={\begin{bmatrix}2&15\\15&1\end{bmatrix}}.}$

モジュラー演算のおかげで要素が非負であることに注目してください。パーマネントを計算するのは簡単です。

${\displaystyle \operatorname {Perm} (A')=2\cdot 1+15\cdot 15=227}$

それで${\displaystyle P=227{\bmod {1}}7=6}$。 それから${\displaystyle P<Q/2}$、 それで${\displaystyle \operatorname {Perm} (A)=P=6.}$

任意の数は2 のべき乗の和に分解できることに注意してください。たとえば、

${\displaystyle 13=2^{3}+2^{2}+2^{0}}$

この事実は、非負行列を、すべての要素が2のべき乗である等価な行列に変換するために利用されます。この変換は、元の行列と等価なグラフを用いて表現できます。

させて${\displaystyle G}$になる${\displaystyle n}$非負の重みを持つ -ノード重み付き有向グラフ、最大の重みは${\displaystyle W}$あらゆる端${\displaystyle e}$重量${\displaystyle w}$は、以下のように2のべき乗の重みを持つ同等のエッジに変換されます。

${\displaystyle w=2^{x_{1}}+2^{x_{2}}+\cdots +2^{x_{r}}}$、${\displaystyle 0\leq x_{1}\leq x_{2}\leq \cdots \leq x_{r}\leq \log(w)}$

これは図1にグラフで示されている。既存のエッジを置き換えるサブグラフには${\displaystyle r}$ノードと${\displaystyle 3r}$端。

これが同等のグラフを生成することを証明する${\displaystyle G'}$オリジナルと同じ永久性を持つものについては、サイクルカバー間の対応関係を示す必要があります。${\displaystyle G}$そして${\displaystyle G'}$。

自転車カバーを検討してみては？${\displaystyle R}$で${\displaystyle G}$。

• エッジ${\displaystyle e}$は${\displaystyle R}$すると、新しいサブグラフのすべてのノードをカバーするには、自己ループを使用する必要があります。すべての自己ループの重みは 1 なので、サイクルカバーの重みは${\displaystyle R}$そして${\displaystyle R'}$マッチ。
• もし${\displaystyle e}$は${\displaystyle R}$すると、対応するすべてのサイクルカバーにおいて${\displaystyle G'}$そこからの道があるはずだ${\displaystyle u}$に${\displaystyle v}$、 どこ${\displaystyle u}$そして${\displaystyle v}$エッジのノードは${\displaystyle e}$構造から、次のことがわかる。${\displaystyle r}$異なる経路が存在し、これらの経路の合計は元のグラフのエッジの重みに等しい。${\displaystyle G}$。したがって、対応するサイクルカバーの重量は${\displaystyle G}$そして${\displaystyle G'}$マッチ。

サイズに注意してください${\displaystyle G'}$は多項式である${\displaystyle n}$そして${\displaystyle \log W}$。

ここでの目的は、要素が2のべき乗である行列を、0と1のみを含む同等の行列（つまり、各辺の重みが1である有向グラフ）に縮小することです。

させて${\displaystyle G}$になる${\displaystyle n}$-ノード有向グラフで、エッジのすべての重みが2のべき乗である。グラフを構築します。${\displaystyle G'}$各エッジの重みは 1 であり、${\displaystyle \operatorname {Perm} (G)=\operatorname {Perm} (G')}$この新しいグラフのサイズは、${\displaystyle (G')}$は、${\displaystyle n}$そして${\displaystyle p}$グラフ内の任意のエッジの最大重み${\displaystyle G}$は${\displaystyle 2^{p}}$。

この削減は各エッジで局所的に行われます。${\displaystyle G}$重みが1より大きいもの。${\displaystyle e=(u,v)}$優位に立つ${\displaystyle G}$重さ${\displaystyle w=2^{r}>1}$サブグラフに置き換えられます。${\displaystyle J_{e}}$それは${\displaystyle 2r}$ノードと${\displaystyle 6r}$図2に示すエッジ。各エッジは${\displaystyle J_{e}}$重みは 1 です。したがって、結果として得られるグラフは${\displaystyle G'}$重みが1の辺のみを含む。

自転車カバーを検討してみては？${\displaystyle R}$で${\displaystyle G}$。

• 元のエッジ${\displaystyle e}$グラフから${\displaystyle G}$は${\displaystyle R}$新しいサブグラフを通るパスを作成することはできません${\displaystyle J_{e}}$サイクルカバーを形成する唯一の方法は${\displaystyle J_{e}}$このような場合、サブグラフ内の各ノードが自己ループを取ることになります。各エッジの重みは1なので、結果として得られるサイクルカバーの重みは元のサイクルカバーの重みと等しくなります。
• しかし、エッジが${\displaystyle G}$サイクルカバーの一部である場合、どのサイクルカバーでも${\displaystyle G'}$道があるはずだ${\displaystyle u}$に${\displaystyle v}$サブグラフ内では、サブグラフを下る各ステップで、そのようなパスを形成するために2つの選択肢があります。この選択をしなければなりません。${\displaystyle r}$回数、結果として${\displaystyle 2^{r}}$から可能な経路${\displaystyle u}$に${\displaystyle v}$したがって、${\displaystyle 2^{r}}$可能なサイクルカバーは複数あり、各パスの重みは1なので、これらのサイクルカバーすべての重みの合計は、元のサイクルカバーの重みと等しくなります。