論文の概要: Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity

• arxiv url: http://arxiv.org/abs/2505.19648v1
• Date: Mon, 26 May 2025 08:04:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:43.26653
• Title: Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity
• Title（参考訳）: 二次遅延複素数を持つ2変数論理のモデル列挙
• Authors: Qiaolan Meng, Juhua Pu, Hongting Niu, Yuyi Wang, Yuanhong Wang, Ondřej Kuželka,
• Abstract要約: 2変数(FO2$)を持つ一階述語論理の関数自由有限領域フラグメントのモデル列挙問題について検討する。 サイズ$n$のドメイン上で$Gamma$のすべてのモデルを列挙するにはどうすればよいのか?
• 参考スコア（独自算出の注目度）: 6.164137092509227
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the model enumeration problem of the function-free, finite domain fragment of first-order logic with two variables ($FO^2$). Specifically, given an $FO^2$ sentence $\Gamma$ and a positive integer $n$, how can one enumerate all the models of $\Gamma$ over a domain of size $n$? In this paper, we devise a novel algorithm to address this problem. The delay complexity, the time required between producing two consecutive models, of our algorithm is quadratic in the given domain size $n$ (up to logarithmic factors) when the sentence is fixed. This complexity is almost optimal since the interpretation of binary predicates in any model requires at least $\Omega(n^2)$ bits to represent.
• Abstract（参考訳）: 2変数(FO^2$)の1階論理の関数自由有限領域フラグメントのモデル列挙問題について検討する。 具体的には、$FO^2$文$\Gamma$と正の整数$n$を与えられた場合、どのようにして$\Gamma$のすべてのモデルを$n$のドメイン上で列挙できるのか? 本稿では,この問題に対処する新しいアルゴリズムを考案する。 我々のアルゴリズムの2つの連続するモデルを生成するのに必要な遅延複雑性は、文が固定されたときに与えられたドメインサイズ$n$(対数因子まで)で二次的である。 この複雑さは、任意のモデルにおける二進述語解釈が表現するために少なくとも$\Omega(n^2)$ bitsを必要とするため、ほぼ最適である。

関連論文リスト

• A direct optimization algorithm for input-constrained MPC [3.0992677770545254]
  この技術ノートは、入力制約付きMPC問題を考察し、その結果のボックス制約付きQPの構造を利用する。 提案アルゴリズムの反復回数はテキストのみに依存していることを示す。 提案アルゴリズムの実行時認証能力は,オープンループ不安定AFTI-16例を用いて理論的,数値的に検証する。
  論文  参考訳（メタデータ） (2023-06-26T21:39:14Z)
• On Exact Sampling in the Two-Variable Fragment of First-Order Logic [8.784424696800214]
  ドメインサイズで時間内に実行される$mathbfFO2$のサンプリングアルゴリズムが存在することを示す。 提案手法は構築的であり,得られたサンプリングアルゴリズムは様々な領域に応用できる可能性がある。
  論文  参考訳（メタデータ） (2023-02-06T12:15:41Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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