抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
数十年間,多くの努力が,その充足可能性が多項式時間で決定できるCNF式のクラスの同定に払われてきた。古典的結果は,Horn式(Aspvall,Plass,およびTarjan,1979)およびKrom(すなわち,2CNF)式(DowlingおよびGallier,1984)の線形-時間扱いやすさである。Williams GomesとSelman(2003)によって導入されたバックドアは,そのような扱いやすいクラスをクラスへの有界距離のすべての公式に徐々に拡張する。バックドアサイズは,公式と扱いやすいクラスの間の自然だがむしろ粗い距離尺度を提供する。M”{a}hlmann,Siebertz,およびVigny(2021)によって導入されたバックドア深さは,より精密な距離測度であり,それは,並列のBoundedバックドアサイズにおける異なるバックドア変数の利用を,有界バックドア深さを意味するが,しかし,一定のバックドア深さと任意に大きなバックドアサイズの公式がある。著者らは,FPT近似アルゴリズムを提案して,クラスHornとKromへのバックドア深さを計算した。これにより,これらのクラスへの有界バックドア深さの公式の充足可能性を決定する線形時間アルゴリズムを導いた。このFPT近似アルゴリズムを障害物の精巧な概念にベースとし,M′′{a}hlmannらの障害物ツリーを,分離器障害物の付加を含む種々の方法で拡張した。バックドアに関する推論を単純化する新しいゲーム理論フレームワークを通してアルゴリズムを開発した。最後に,有界バックドア深さは既知の方法で捉えられないCNF公式の扱いやすいクラスを捉えることを示した。【JST・京大機械翻訳】
