FKTは普遍的ではない  対称制約のための平面Holant二分法【JST・京大機械翻訳】

Cai Jin-Yi; Fu Zhiguo; Guo Heng; Williams Tyson

文献

J-GLOBAL ID：202202290735557698 整理番号：22A0623815

FKTは普遍的ではない対称制約のための平面Holant二分法【JST・京大機械翻訳】

FKT is Not Universal - A Planar Holant Dichotomy for Symmetric Constraints

出版者サイト複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=22A0623815&from=J-GLOBAL&jstjournalNo=D0592A") }}

著者 (4件)： , , ,
資料名：
巻： 66 号： 1 ページ： 143-308 発行年： 2022年
JST資料番号： D0592A ISSN： 1432-4350 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：ドイツ (DEU) 言語：英語 (EN)

Boole変数に対する複素値対称制約関数の任意の集合によって定義されるHolant問題に対する複雑性分類を証明した。これは,一般的グラフで扱いにくい平面グラフ上の問題に対する多項式時間アルゴリズムを得るための汎用戦略である,ホログラフィック変換(Valiant,SIAM J.Comput.37(5),1565~15942008)の下で,Fisher-Kasteleyn-Temperley(FKT)アルゴリズムに特に答える。一般的グラフでは#P困難であるが,平面グラフでは多項式時間可解性がある。スピンシステム(Kowalczyk 2010)および計数制約充足問題(#CSP)(GuoおよびWilliams,J.Comput.Sci.Sci.107,1-22020)に対して,再発生テーマは,FKTへのホログラフィック低減がこれらの問題を正確に捉えることを明らかにした。驚くべきことに,Holantに対しては,FKTに対するホログラフィック低減によって表現できない新しい平面可能な問題を発見した。特に,上記の再帰テーマに沿った平面Holant問題のための二分法の直接定式化は,偽である。#CSPdのための二分法定理は,あらゆる変数が複数のd時間に現れる#CSPを表示し,以前の研究で重要なツールである。しかし,#CSPd二分切断に対する証明は平面性に違反し,平面の場合に容易に一般化しない。事実,著者らの新しく発見された扱いやすい問題により,平面#CSPd二分切断の推定型は,d≧5のとき,偽である。それにもかかわらず,平面#CSP2に対する二分切開を証明した。この場合,二分切開の推定形式は真実である。d≧3のより一般的な平面#CSPd二分法に頼らず,この平面#CSP2二分切開のみに依存する平面Holant dichotomyの証明を管理した。新しい多項式時間計算可能問題の特殊ケースは,入射グラフが平面でk≧5のとき,k均一超グラフ上の完全マッチング(#PM)を計数する。同じ問題は,k=3またはk=4のとき,#P-ハードであり,それはまた,著者らの二分切断の結果である。k=2のとき,それは平面グラフ上で#PMとなり,再び扱いやすい。より一般的には,特定のハイパーエッジサイズと同じ平面性仮定を有する超グラフ上で,すべてのハイパーエッジサイズの最大の共通ディバイザ(gcd)が少なくとも5であるならば,#PMは多項式時間計算可能である。それは,それがgcdであり,超エッジサイズに結合せず,それは扱いやすさの判定基準である。Copyright The Author(s) 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

著者キーワード (3件)： , ,

グラフ理論基礎 , その他のオペレーションズリサーチの手法 , 計算理論

前のページに戻る

FKTは普遍的ではない 対称制約のための平面Holant二分法【JST・京大機械翻訳】

FKTは普遍的ではない対称制約のための平面Holant二分法【JST・京大機械翻訳】