抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
主-SAT(a.k.a.MAJ-SAT)は,連結正規形式(CNF)における入力n変数式が少なくとも2^(n-1)の割り当てを満たすかどうかを決定する問題である。確率的計画と推論の複雑性に関心を持つ様々なAIコミュニティにおいて,主要なSATと関連問題が広く研究されている。Majority-SATは40年以上にわたってPP完全であることが知られているが,自然変異体の複雑性は未解決のままであり,そこでは,入力CNF公式が,ほとんどのkで節幅を持つように制約されている。著者らは,あらゆるkに対して,Majority-kSATがPであることを示した。事実,この問題は線形時間で解くことができる。より一般的には,有界デノミネータを持つ(0,1)の任意の正の整数kと定数pに対して,与えられたk-CNFが,決定論的線形時間で,少なくともp(2^n)充足を満たすかどうかを決定するアルゴリズムを与える。CNF式に硬い多くの類似問題は3-CNFsに限定された場合,硬くなるので,これらの結果が驚くべきことが分かった。著者らのアルゴリズムは,複雑性と推論の複雑性を計数するのに,興味深い正の含意を持ち,E-MAJ-kSATとMAJ-kSATのような関連する問題の既知の複雑性を著しく減らした。結果は,パリティkの制約で任意のBoole CSPsに直ちに拡張する。本アプローチの心臓では,k-CNFの対応するセットシステムに見られる様々なヒマワリを抽出し,解析することによって閾値計数問題を解くための効率的な方法である。著者らの結果の意味を探索して,著者らは,主要性-kSATの扱いやすさが,興味深い方法で幾分脆弱であることを発見した。密接に関連するGtMajority-SAT問題(ここで,与えられた公式が2^(n-1)を満たすかどうか)はPP完全であることが知られているが,GtMajority-kSATは,ほとんどの3でkに対してPにあるが,kは少なくとも4でNP完全になることを示す。また,任意の幅の1つの付加的節理を有するk-CNFs上のMajority-SATに対して,この問題はk=3に対してPP完全であり,k=3に対してはNP困難であり,k=2に対してはPに留まることを示した。これらの結果は,これらの問題の”自然”分類がPP完全性であり,少なくとも4の全てのkに対してGtMajority-kSATとMajority-kSATの複雑性に恒星差があるので,直観的である。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
