論文の概要: Complexity of Contextuality

• arxiv url: http://arxiv.org/abs/2506.09133v1
• Date: Tue, 10 Jun 2025 18:00:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 06:35:01.82703
• Title: Complexity of Contextuality
• Title（参考訳）: コンテクストの複雑さ
• Authors: Theodoros Yianni, Farid Shahandeh,
• Abstract要約: 一般化された文脈性は、量子力学のような非古典理論の目印である。 次元$k$の非文脈的存在論的モデルの存在を決定する複雑さは、少なくとも理論の次元において指数関数的である。 また、最小の非文脈オントロジモデルと最小のオントロジモデルとの根本的な違いを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generalized contextuality is a hallmark of nonclassical theories like quantum mechanics. Yet, three fundamental computational problems concerning its decidability and complexity remain open. First, determining the complexity of deciding if a theory admits a noncontextual ontological model; Second, determining the complexity of deciding if such a model is possible for a specific dimension $k$; Third, efficiently computing the smallest such model when it exists, given that finding the smallest ontological model is NP-hard. We address the second problem by presenting an algorithm derived from a geometric formulation and its reduction to the intermediate simplex problem in computational geometry. We find that the complexity of deciding the existence of a noncontextual ontological model of dimension $k$ is at least exponential in the dimension of the theory and at most exponential in $k$. This, in turn, implies that computing the smallest noncontextual ontological model is inefficient in general. Finally, we demonstrate the fundamental difference between finding the smallest noncontextual ontological model and the smallest ontological model using an explicit example wherein the respective minimum ontic sizes are five and four.
• Abstract（参考訳）: 一般化された文脈性は、量子力学のような非古典理論の目印である。 しかし、決定可能性と複雑性に関する3つの基本的な計算問題は未解決のままである。 第一に、理論が非文脈的存在論的モデルを認めるかどうかを決定する複雑さを決定すること、第二に、そのようなモデルが特定の次元$k$に対して可能であるかどうかを決定する複雑さを決定すること、第三に、最小の存在論的モデルを見つけることがNPハードであることを考えると、そのモデルが存在するとき、より効率的な計算を行うことである。 本稿では,幾何学的定式化から導出したアルゴリズムを計算幾何学の中間的単純問題に還元することで,この問題に対処する。 次元$k$の非文脈的存在論的モデルの存在を決定する複雑さは、理論の次元において少なくとも指数関数であり、少なくとも$k$の指数関数である。 これは逆に、最小の非文脈的存在論モデルを計算することは一般に非効率的であることを意味する。 最後に,最小の非文脈オントロジーモデルと最小のオントロジーモデルとの基本的な違いを,各最小のオントティックサイズが5と4である明示的な例を用いて示す。

関連論文リスト

• A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds [6.6362553223890535]
  我々は、見過ごされているように見えるが自然なパラメータ n の下で、難解な誘引問題の複雑さを分析する。 SigmaP$ と NP- および coNP-完全 フラグメントに対していくつかの正の値が得られる。 我々はこれを低い境界で補い、多くのフラグメントは(強い)指数時間仮説の下で改善を除外する。
  論文  参考訳（メタデータ） (2025-05-15T11:56:19Z)
• The Limits of AI Explainability: An Algorithmic Information Theory Approach [4.759142872591625]
  本稿では,アルゴリズム情報理論によるAI説明可能性の基本的限界を理解するための理論的基盤を確立する。 複素モデルの近似として説明可能性の形式化を行い、コルモゴロフを用いた近似誤差と説明の定量化を行う。 結果は、説明可能なAIシステムの設計、評価、監視に関連すると思われる考慮事項を強調している。
  論文  参考訳（メタデータ） (2025-04-29T11:58:37Z)
• Cover Learning for Large-Scale Topology Representation [0.0]
  本稿では,幾何学的データセットのトポロジ的に忠実な被覆を学習する手法について述べる。 そこで得られた単純複体は, 標準トポロジカル推論手法よりも, サイズ的に優れていることを示す。
  論文  参考訳（メタデータ） (2025-03-12T19:10:20Z)
• Topological Representational Similarity Analysis in Brains and Beyond [15.417809900388262]
  この論文では、神経表現の幾何学的および位相的特性を組み合わせた新しいフレームワークであるトポロジカルRSA(tRSA)を紹介する。 tRSAは非線型単調変換を表現上の相似性に適用し、中間スケールの幾何学を維持しながら局所位相を強調する。 結果として生じる地形行列は、ノイズや個々の慣用性に頑健なモデル比較を可能にする。
  論文  参考訳（メタデータ） (2024-08-21T19:02:00Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Structure Learning and Parameter Estimation for Graphical Models via Penalized Maximum Likelihood Methods [0.0]
  論文では、静的なベイジアンネットワーク(BN)と、その名前が示すように時間成分を持つ連続時間ベイジアンネットワークという2つの異なるタイプのPGMについて考察する。 私たちは、PGMを学ぶための最初のステップである、真の構造を回復することに興味を持っています。
  論文  参考訳（メタデータ） (2023-01-30T20:26:13Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)

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

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