論文の概要: Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning

• arxiv url: http://arxiv.org/abs/2405.18548v3
• Date: Tue, 25 Feb 2025 06:37:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-26 17:42:44.134977
• Title: Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
• Title（参考訳）: トランスフォーマーエンコーダの満足度:複雑さと形式的推論への影響
• Authors: Marco Sälzer, Eric Alsmann, Martin Lange,
• Abstract要約: 我々は、変換器エンコーダ(TE)における満足度問題、または同様の実現可能性問題(trSAT)の複雑さを解析する。 表現性コミュニティで一般的に研究されている TE を考えると,trSAT は決定不可能であることがわかった。 trSATが決定可能な現実シナリオを特定し,それに対応する複雑性境界を確立する。
• 参考スコア（独自算出の注目度）: 4.096453902709292
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyse the complexity of the satisfiability problem, or similarly feasibility problem, (trSAT) for transformer encoders (TE), which naturally occurs in formal verification or interpretation, collectively referred to as formal reasoning. We find that trSAT is undecidable when considering TE as they are commonly studied in the expressiveness community. Furthermore, we identify practical scenarios where trSAT is decidable and establish corresponding complexity bounds. Beyond trivial cases, we find that quantized TE, those restricted by fixed-width arithmetic, lead to the decidability of trSAT due to their limited attention capabilities. However, the problem remains difficult, as we establish scenarios where trSAT is NEXPTIME-hard and others where it is solvable in NEXPTIME for quantized TE. To complement our complexity results, we place our findings and their implications in the broader context of formal reasoning.
• Abstract（参考訳）: 本稿では,形式的検証や解釈において自然に発生する変圧器エンコーダ(TE)の満足度問題,あるいは同様の実現可能性問題(trSAT)の複雑性を解析し,これを形式的推論と呼ぶ。 表現性コミュニティで一般的に研究されている TE を考えると,trSAT は決定不可能であることがわかった。 さらに, trSAT が決定可能な現実シナリオを特定し, 対応する複雑性境界を確立する。 自明なケース以外にも、固定幅演算によって制限された量子化TEは、その注意力の制限により、trSATの決定可能性をもたらす。 しかし、trSAT が NEXPTIME-hard であるシナリオや、量子化 TE の NEXPTIME で解決可能なシナリオを確立するため、この問題は依然として困難である。 複雑化の結果を補完するため, 形式的推論のより広い文脈に発見とその意味を配置した。

関連論文リスト

• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化 正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。 新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
  論文  参考訳（メタデータ） (2025-04-02T17:45:58Z)
• Self-Satisfied: An end-to-end framework for SAT generation and prediction [0.7340017786387768]
  高速SAT問題生成のためのハードウェアアクセラレーションアルゴリズムと幾何SAT符号化を導入する。 これらの進歩により、何千もの変数と数万の節でSAT問題へのアプローチをスケールできます。 私たちの研究の基本的な側面は、SATデータの本質と、機械学習モデルのトレーニングに適合する可能性に関するものです。
  論文  参考訳（メタデータ） (2024-10-18T22:25:54Z)
• Solving the Challenge Set without Solving the Task: On Winograd Schemas as a Test of Pronominal Coreference Resolution [21.19369044026899]
  我々は,Winograd Challenge セットにおける言語モデル (LM) の強い性能にもかかわらず,OntoNotes で実証されたある種の固有曖昧性を解決する上で,これらのモデリング手法は比較的貧弱であることを示す。 提案手法は,各データセット間での固有コアの解法において,総合的に高精度な教師付きタスク固有システムを用いて,誘導型LMをアンサンブルする方法である。
  論文  参考訳（メタデータ） (2024-10-12T09:04:53Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。 量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか? QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
  論文  参考訳（メタデータ） (2023-09-28T13:30:20Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  並列量子SATソルバは,線形時間 O(m) から定数時間 O(1) までの繰り返しの時間複雑性を,余分な絡み合った量子ビットを用いて低減する。 我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。
  論文  参考訳（メタデータ） (2023-08-07T06:52:06Z)
• Evolutionary Diversity Optimisation in Constructing Satisfying Assignments [20.386139395296215]
  本稿では,EDOの文脈におけるブール充足可能性問題(SAT)について検討する。 SATは計算機科学において非常に重要であり、KPやTSPといったEDO文献で研究されている他の問題とは異なる。 本稿では,SAT解の集合間の多様性を明示的に最大化するために,よく知られたSATソルバを用いた進化的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-19T06:26:10Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Circuit Complexity through phase transitions: consequences in quantum state preparation [0.0]
  量子多体系の基底状態を作成するための回路の複雑さを解析する。 特に、基底状態が量子相転移に近づくにつれて、この複雑さがどのように成長するか。
  論文  参考訳（メタデータ） (2023-01-11T19:00:10Z)
• 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)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。 ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
  論文  参考訳（メタデータ） (2022-03-02T05:14:12Z)
• Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability [30.01308882849197]
  本稿では,アルゴリズム推論データセットを作成するための新しい手法を提案する。 鍵となる考え方は、ハードプロポーズSAT問題の経験的なサンプリングや、言語に関する複雑性理論的な研究から洞察を得ることである。 十分なトレーニングデータを得た現在のトランスフォーマーは、結果のNLSat問題を解決するのに驚くほど堅牢であることがわかった。
  論文  参考訳（メタデータ） (2021-12-16T17:47:20Z)
• From LSAT: The Progress and Challenges of Complex Reasoning [56.07448735248901]
  本稿では,LSAT(Law School Admission Test)の3つの課題について,解析的推論,論理的推論,読解の3つの課題について検討する。 本稿では,これら3つのタスクを統合するハイブリッド推論システムを提案する。
  論文  参考訳（メタデータ） (2021-08-02T05:43:03Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Comprehensible Counterfactual Explanation on Kolmogorov-Smirnov Test [56.5373227424117]
  我々は,KSテストに失敗するテストデータに対して,反実的説明を生成する問題に対処する。 我々は、KSテストに失敗したテストセットの指数的なサブセット数を列挙し、チェックするのを避ける効率的なアルゴリズムMOCHEを開発した。
  論文  参考訳（メタデータ） (2020-11-01T06:46:01Z)
• Pareto Probing: Trading Off Accuracy for Complexity [87.09294772742737]
  我々は,プローブの複雑性と性能の基本的なトレードオフを反映したプローブ計量について論じる。 係り受け解析による実験により,文脈表現と非文脈表現の統語的知識の幅広いギャップが明らかとなった。
  論文  参考訳（メタデータ） (2020-10-05T17:27:31Z)

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

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