論文の概要: MAJORITY-3SAT (and Related Problems) in Polynomial Time
- arxiv url: http://arxiv.org/abs/2107.02748v1
- Date: Tue, 6 Jul 2021 17:24:04 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-07 16:15:24.204861
- Title: MAJORITY-3SAT (and Related Problems) in Polynomial Time
- Title（参考訳）: 多項式時間におけるMAJORITY-3SAT(と関連する問題)
- Authors: Shyan Akmal and Ryan Williams
- Abstract要約: 与えられた$k$-CNFが有界分母を持つ少なくとも$rho in (0,1)$を持つか否かを決定するアルゴリズムを与える。
我々のアルゴリズムは、複雑性と推論の複雑さを数えることに興味深いポジティブな意味を持っている。
- 参考スコア（独自算出の注目度）: 4.035753155957698
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Majority-SAT is the problem of determining whether an input $n$-variable
formula in conjunctive normal form (CNF) has at least $2^{n-1}$ satisfying
assignments. Majority-SAT and related problems have been studied extensively in
various AI communities interested in the complexity of probabilistic planning
and inference. Although Majority-SAT has been known to be PP-complete for over
40 years, the complexity of a natural variant has remained open:
Majority-$k$SAT, where the input CNF formula is restricted to have clause width
at most $k$.
We prove that for every $k$, Majority-$k$SAT is in P. In fact, for any
positive integer $k$ and rational $\rho \in (0,1)$ with bounded denominator, we
give an algorithm that can determine whether a given $k$-CNF has at least $\rho
\cdot 2^n$ satisfying assignments, in deterministic linear time (whereas the
previous best-known algorithm ran in exponential time). Our algorithms have
interesting positive implications for counting complexity and the complexity of
inference, significantly reducing the known complexities of related problems
such as E-MAJ-$k$SAT and MAJ-MAJ-$k$SAT. At the heart of our approach is an
efficient method for solving threshold counting problems by extracting
sunflowers found in the corresponding set system of a $k$-CNF.
We also show that the tractability of Majority-$k$SAT is somewhat fragile.
For the closely related GtMajority-SAT problem (where we ask whether a given
formula has greater than $2^{n-1}$ satisfying assignments) which is known to be
PP-complete, we show that GtMajority-$k$SAT is in P for $k\le 3$, but becomes
NP-complete for $k\geq 4$. These results are counterintuitive, because the
``natural'' classifications of these problems would have been PP-completeness,
and because there is a stark difference in the complexity of GtMajority-$k$SAT
and Majority-$k$SAT for all $k\ge 4$.
- Abstract（参考訳）: Majority-SAT は、入力 $n$-variable formula in conjunctive normal form (CNF) が割り当てを満たす少なくとも 2^{n-1}$ を持つかどうかを決定する問題である。
マジョリティSATと関連する問題は、確率的計画と推論の複雑さに関心を持つ様々なAIコミュニティで広く研究されている。
Majority-SAT は 40 年以上にわたって PP 完全であることが知られているが、自然変分法の複雑さは開のままである: Majority-$k$SAT は入力 CNF 公式が最大で k$ の節幅を持つように制限されている。
実のところ、任意の正の整数 $k$ と有理の$\rho \in (0,1)$ に対して、与えられた$k$-cnf が少なくとも$\rho \cdot 2^n$ を満たす代入を持つかどうかを決定論的線形時間で決定できるアルゴリズムを与える。
我々のアルゴリズムは、複雑性と推論の複雑さを数えることに興味深いポジティブな意味を持ち、e-maj-$k$sat や maj-maj-$k$sat のような関連する問題の既知の複雑さを著しく減少させる。
提案手法の核心は, 対応するセットシステムである$k$-CNFのサンフラワーを抽出することにより, しきい値計数問題の解法である。
また、Majority-$k$SATのトラクタビリティがやや脆弱であることも示します。
密接な関係にある gtmajority-sat 問題(与えられた公式が 2^{n-1}$ 以上の満足する代入を持つかどうかを問う場合)に対して、gtmajority-$k$sat は p において $k\le 3$ であるが、$k\geq 4$ で np-complete となる。
これらの結果は直感的ではない、なぜならこれらの問題の ``natural'' 分類は PP-完全性 であり、またすべての$k\ge 4$に対して GtMajority-$k$SAT と Majority-$k$SAT の複雑さに大きな違いがあるからである。
関連論文リスト
- The Computational Complexity of Finding Stationary Points in Non-Convex
Optimization [60.53870185393238]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。
また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文 参考訳（メタデータ） (2022-02-11T23:53:43Z) - The Algorithmic Phase Transition of Random $k$-SAT for Low Degree
Polynomials [18.00315760946089]
満足な代入は、節密度$m/n 2k log 2 - frac12で高い確率で存在することが知られている。
低次アルゴリズムは節密度$(1 - o_k(1)) 2k log k / k$で満足な代入を見つけることができる。
論文 参考訳（メタデータ） (2021-06-03T21:01:02Z) - Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
論文 参考訳（メタデータ） (2021-02-19T01:42:50Z) - Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT [0.0]
本稿では,最大3-Stisfiability (MAX-E-$3$-SAT) 問題に対して$Theta(N)$で近似解を計算するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-10T07:59:54Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。