論文の概要: SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set
- arxiv url: http://arxiv.org/abs/2604.19947v1
- Date: Tue, 21 Apr 2026 19:50:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-23 15:36:10.771783
- Title: SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set
- Title（参考訳）: SAT + NAUTY: 最小状態独立性集合を含む小コチェンスペクトル集合の順序生成
- Authors: Zhengyu Li, Curtis Bright, Stefan Trandafir, Adán Cabello, Vijay Ganesh,
- Abstract要約: 3 次元の小さな Kochen-Specker (KS) 集合を探索する。
我々は13線Yu-Oh集合の拡張を目標としており、これは状態に依存しない文脈性に対する最小の証人であることが証明されている。
- 参考スコア（独自算出の注目度）: 9.824030987991497
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a search for small Kochen-Specker (KS) sets in dimension 3, specifically targeting extensions of the 13-ray Yu-Oh set, which has been proven to be the minimal witness to state-independent contextuality. To enable this search, we introduce a novel SAT-based orderly generation framework integrating recursive canonical labeling (RCL) with the graph isomorphism tool NAUTY. We demonstrate that previous SAT approaches relying on lexicographical canonicity suffer from exponential scaling on canonical graphs. This limitation renders them intractable on the large instances (25 to 33 vertices) encountered in our search, whereas our RCL check maintains consistent millisecond-level performance, effectively eliminating the bottleneck. Overcoming this bottleneck allows us to perform the first exhaustive enumeration of all KS sets with up to 33 rays containing the complete 25-ray state-independent contextuality (SI-C) set obtained by rigid extensions of the Yu-Oh set in 1,641 CPU hours. We found and verified that the 33-ray set discovered by Schütte is the smallest three-dimensional KS set containing the complete 25-ray SI-C set. All non-existence results are backed by independently verifiable proof certificates via an extension of the DRAT proof format.
- Abstract（参考訳）: 3次元の小さな Kochen-Specker (KS) 集合を探索し、特に13線Yu-Oh 集合の拡張を対象としており、これは状態非依存の文脈性に対する最小の証人であることが証明されている。
この探索を可能にするために、再帰的正準ラベル付け(RCL)とグラフ同型ツールNAUTYを組み合わせた新しいSATベースの順序生成フレームワークを提案する。
本研究では,レキシカルな正準性に依存する従来のSATアプローチが,正準グラフの指数的スケーリングに悩まされていることを実証する。
この制限は、検索で遭遇する大きなインスタンス(25から33の頂点)で引き起こされるが、我々のRCLチェックは、一貫したミリ秒レベルのパフォーマンスを維持し、ボトルネックを効果的に排除する。
このボトルネックを克服することで、1,641CPU時間でYu-Oh集合の厳密な拡張によって得られた完全な25線状態独立文脈性(SI-C)を含む最大33個のKS集合の完全な列挙を行うことができる。
シュッテによって発見された33光集合は、完全な25光SI-Cを含む最小の3次元KS集合であることを発見し、検証した。
全ての非存在結果は、DRAT証明フォーマットの拡張を通じて独立に検証可能な証明証明によって裏付けられる。
関連論文リスト
- Finding Belief Geometries with Sparse Autoencoders [0.0]
本稿では,変圧器表現における単純な部分空間の候補を求めるパイプラインを提案する。
隠れマルコフモデルを用いて学習した変圧器上でのパイプラインの検証を行った。
真の信念のような幾何学がGemma-2-9Bの表現空間に存在するという予備的な証拠がある。
論文 参考訳（メタデータ） (2026-04-03T03:29:48Z) - On Simplest Kochen-Specker Sets [0.0]
任意の次元における最も単純な文脈集合の意味、起源、重要性を分析する。
基本ベクトル成分からの文脈集合の自動生成は、任意の次元の任意の種類の既知の最小文脈集合を自動生成することを示す。
最後に、文脈集合、特にKochen-Specker (KS)、拡張KS、非KS、およびそれらの定義のあいまいさについて論じる。
論文 参考訳（メタデータ） (2025-12-11T10:01:34Z) - Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm [64.43268969806098]
モンテカルロ木探索(MCTS)の中核的な課題は、状態-作用ペアをグループ化することで改善できるサンプル効率である。
我々は、値等価状態または状態-作用ペアをグループ化し、代わりに異なる値を持つグループ状態と状態-作用ペアをグループ化するパラダイムを破る。
我々はこの抽象化フレームワークをKVDA(Known Value difference Abstractions)と呼び、即時報酬の分析によって価値の差を推測する。
論文 参考訳（メタデータ） (2025-10-29T11:03:44Z) - CLUE: Non-parametric Verification from Experience via Hidden-State Clustering [64.50919789875233]
隠れアクティベーションの軌跡内の幾何的に分離可能なシグネチャとして解の正しさが符号化されていることを示す。
ClUE は LLM-as-a-judge ベースラインを一貫して上回り、候補者の再選において近代的な信頼に基づく手法に適合または超えている。
論文 参考訳（メタデータ） (2025-10-02T02:14:33Z) - Light-SQ: Structure-aware Shape Abstraction with Superquadrics for Generated Meshes [60.92139345612904]
我々は、新しいスーパークワッドリックベースの最適化フレームワークLight-SQを提案する。
本稿では,構造対応ボリューム分解によるブロック再配置戦略を提案する。
実験によると、Light-SQはスーパークワッドリックで効率よく、高忠実で、編集可能な形状の抽象化を可能にする。
論文 参考訳（メタデータ） (2025-09-29T16:18:32Z) - SeqCSIST: Sequential Closely-Spaced Infrared Small Target Unmixing [7.09321729956876]
本研究では,高密度CSISTグループからのサブピクセルローカライゼーションの形で全ターゲットを検出するための新しいタスクであるSequential CSIST Unmixingを提案する。
我々は、シーケンシャルなベンチマークデータセットであるSeqCSISTや、この特別なタスクに対する客観的評価指標を提供するツールキットなど、オープンソースのエコシステムにコントリビュートする。
平均精度(mAP)は5.3%向上した。
論文 参考訳（メタデータ） (2025-07-13T09:59:48Z) - Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption [0.0]
量子論の2つの基本構造が2つの剛KS集合を定義することを示す。
2つ目の構成は最小のKS問題を解く手がかりを提供する。
我々は、31が最小のKS集合問題の解であると予想する。
論文 参考訳（メタデータ） (2025-01-20T18:13:28Z) - ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion [78.8942067357231]
ExpressivEは、一対の実体を点として埋め込み、仮想三重空間に超平行グラフとして関係を埋め込む。
我々は、ExpressivEが最先端のKGEと競合し、W18RRでさらに優れています。
論文 参考訳（メタデータ） (2022-06-08T23:34:39Z) - Accelerating DETR Convergence via Semantic-Aligned Matching [50.3633635846255]
本稿では,DTRの精度を犠牲にすることなく,DTRの収束を大幅に加速するセマンティック整合DTRであるSAM-DETRを提案する。
意味整合性マッチングにおいて最も識別性の高い特徴を持つ有能な点を明示的に検索し、収束をさらに高速化し、検出精度も向上する。
論文 参考訳（メタデータ） (2022-03-14T06:50:51Z) - Tensor Representations for Action Recognition [54.710267354274194]
シーケンスにおける人間の行動は、空間的特徴とその時間的ダイナミクスの複雑な相互作用によって特徴づけられる。
アクション認識タスクの視覚的特徴間の高次関係を捉えるための新しいテンソル表現を提案する。
我々は,高次テンソルといわゆる固有値パワー正規化(NEP)を用いて,高次事象のスペクトル検出を行う。
論文 参考訳（メタデータ） (2020-12-28T17:27:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。