論文の概要: Planted-solution SAT and Ising benchmarks from integer factorization

• arxiv url: http://arxiv.org/abs/2604.09837v1
• Date: Fri, 10 Apr 2026 19:09:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:15.701311
• Title: Planted-solution SAT and Ising benchmarks from integer factorization
• Title（参考訳）: 整数分解による植物溶出SATとIsingベンチマーク
• Authors: Itay Hen,
• Abstract要約: 2つの素数 $p$ と $q$ が与えられたとき、構成は、直交正規形式 (CNF) として$N = p times q$ の算術的制約を符号化する。 2つの$d$-bit素数に対して、キャリー収縮の総数は$d4$であることを示す。 この構成は、単一のパラメータで制御され、スケーラブルで構造化され、検証可能なベンチマークファミリを提供する。
• 参考スコア（独自算出の注目度）: 0.06768558752130309
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a family of planted-solution benchmark instances for satisfiability (SAT) solvers and Ising optimization derived from integer factorization. Given two primes $p$ and $q$, the construction encodes the arithmetic constraints of $N = p \times q$ as a conjunctive normal form (CNF) formula whose satisfying assignments correspond to valid factorizations of~$N$. The known pair $(p,q)$ serves as a built-in ground truth, enabling unambiguous verification of solver output. We show that for two $d$-bit primes the total number of carry contractions is on the order of $d^4$. Empirical benchmarks with SAT solvers show that median runtime grows exponentially in the bit-length of the factors over the range tested. The construction provides a scalable, structured, and verifiable benchmark family controlled by a single parameter, accompanied by open-source generation software.
• Abstract（参考訳）: 本稿では、SAT(SAT)ソルバと整数分解から導かれるIsing最適化のためのプラント・ソリューション・ベンチマーク・インスタンスのファミリーについて述べる。 2つの素数 $p$ と $q$ が与えられたとき、構成は$N = p \times q$ の算術的制約を共役正規形式 (conjunctive normal form, CNF) 公式としてエンコードする。 既知のペア $(p,q)$ は基底真理の組として機能し、ソルバ出力の曖昧な検証を可能にする。 2つの$d$-bit素数に対して、キャリー収縮の総数は$d^4$であることを示す。 SATソルバを用いた実証的なベンチマークでは、テスト範囲の要素のビット長で中央値のランタイムが指数関数的に増加することが示されている。 この構成は、単一のパラメータで制御され、スケーラブルで構造化され、検証可能なベンチマークファミリを提供する。

関連論文リスト

• Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups [0.0]
  有限アーベル群上のゴワーズノルム$Uk$を推定するための量子アルゴリズム群を提案する。 これらのアルゴリズムは、ガウワーズノルムに対する最近の逆定理と振幅推定を利用して高次相関を明らかにする。
  論文  参考訳（メタデータ） (2025-08-02T06:58:12Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• SAT and Lattice Reduction for Integer Factorization [5.035245337299788]
  ランダムリークビット因数分解問題の解法として,新しいハイブリッドSATおよび計算機代数手法を提案する。 我々の実装は、純粋なSATや純粋計算機代数のアプローチよりもはるかに高速なランダムリークビット分解問題を解く。
  論文  参考訳（メタデータ） (2024-06-28T17:30:20Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error [16.075339182916128]
  GPシステムは、必要最小限のコンポーネントが備わっている場合、$n$変数の結合を進化させることができる。 GPシステムは、$O(ell n log2 n)$, $ell geq が受理木の大きさの極限であるような予想において、正確なターゲット関数を進化させることができることを示す。
  論文  参考訳（メタデータ） (2023-03-13T20:24:21Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。 計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
  論文  参考訳（メタデータ） (2020-05-05T12:10:21Z)
• Determining the Multiplicative Complexity of Boolean Functions using SAT [1.4902915966744057]
  ブール関数の乗法的複雑性を決定するための構築的SATアルゴリズムを提案する。 提案アルゴリズムは,全5入力アフィン等価クラスの代表に対して最適XAGを求めることができる。
  論文  参考訳（メタデータ） (2020-05-04T18:29:48Z)

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

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