論文の概要: 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 の複雑さに大きな違いがあるからである。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。 また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
  論文  参考訳（メタデータ） (2024-03-05T15:03:47Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。