Fugu-MT 論文翻訳(概要): A Phase Transition in Minesweeper

論文の概要: A Phase Transition in Minesweeper

arxiv url: http://arxiv.org/abs/2008.04116v1
Date: Mon, 10 Aug 2020 13:21:13 GMT
ステータス: 処理完了
システム内更新日: 2022-10-31 23:12:59.789321
Title: A Phase Transition in Minesweeper
Title（参考訳）: 鉱山用スウィーパーの相転移
Authors: Ross Dempsey and Charles Guinn
Abstract要約: ミナスウィーパーの演奏はNP完全であることが知られている。我々はマインズウィーパーがよく研究されたSAT相転移に類似した相転移を示すことを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition.
Abstract（参考訳）: プレイヤーが2次元格子上で鉱山の位置を推定する古典的マインズウィーパーゲームの平均ケース複雑性について検討する。 minesweeperの演奏は共np完全であることが知られている。実験の結果,minesweeperはsat相転移に類似した相転移を示すことがわかった。臨界地雷密度を超えると、論理的推論でマインズウィーパーをプレイすることはほとんど不可能になる。我々は,minesweeperインスタンスの硬さを特徴付けるためにbooleanの不満足さを低減し,位相遷移時に硬さがピークとなることを示す。さらに,Minesweeper推論に対する多項式時間アプローチの位相遷移におけるアルゴリズム的障壁を示す。最後に,相転移の漸近的挙動に対する期待について述べる。

関連論文リスト

Scalable improvement of the generalized Toffoli gate realization using trapped-ion-based qutrits [32.33017977520031]
トフォリゲートの直接実現には、2量子ゲートの数の禁止的な成長が必要か、またはアンシラ量子ビットを使用する必要がある。ここでは、トラップイオンベースのデュアル型光マイクロ波量子ドットを用いたトフォリゲートの実現のスケーラブルな改善を実験的に実証する。
論文参考訳（メタデータ） (2024-07-10T15:34:56Z)
Many-body phase transitions in a non-Hermitian Ising chain [0.8749675983608172]
一次元強磁性トランスバースフィールドIsingモデルにおける多体相転移について検討する。 2次相転移と$mathcalPT$相転移の3つの相転移を示すことを示す。
論文参考訳（メタデータ） (2023-11-19T06:32:12Z)
Many-body entanglement and spectral clusters in the extended hard-core bosonic Hatano-Nelson model [0.0]
ハードコア限界における拡張ボソニック・ハタノ・ネルソンモデルの多体絡みとスペクトルについて検討する。本システムでは, ギャップレス位相から電荷密度波位相への位相遷移と, 1次励起状態における$mathcalPT$遷移が伴うことを示す。
論文参考訳（メタデータ） (2023-10-11T15:39:33Z)
Complexity Transitions in Non-Unitary Boson Sampling Dynamics [0.0]
非エルミート開系における一意的な遷移であるパリティ時間(mathcalPT$)対称性の破れは、ボソンの確率分布をサンプリングする複雑さに大きな影響を及ぼす。 $mathcalPT$-symmetric 相では、ボソンの分布が計算可能な粒子によって近似されなくなるのは1つの動的遷移のみである。
論文参考訳（メタデータ） (2022-07-26T03:02:11Z)
A Probabilistic Interpretation of Transformers [91.3755431537592]
本稿では,変圧器の指数点積注意の確率論的解釈と指数列に基づくコントラスト学習を提案する。我々は、我々の理論とホップフィールド理論の理論的限界を述べ、分解の方向性を提案する。
論文参考訳（メタデータ） (2022-04-28T23:05:02Z)
Determining ground-state phase diagrams on quantum computers via a generalized application of adiabatic state preparation [61.49303789929307]
我々は、状態準備のために局所的な断熱ランプを使用して、時間的進化を通じて量子コンピュータ上の基底状態位相図を直接計算することができる。我々は,IBMの量子マシンを用いて,二つのサイトシステムと3つのサイトシステムの両方の正確な位相図を計算できる。
論文参考訳（メタデータ） (2021-12-08T23:59:33Z)
Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文参考訳（メタデータ） (2021-07-21T17:10:14Z)
Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits [58.720142291102135]
最大21キュービットの雑音量子フーリエ変換プロセッサをシミュレートする。我々は、デジタルエラーモデルに頼るのではなく、微視的な散逸過程を考慮に入れている。動作中の消散機構によっては、入力状態の選択が量子アルゴリズムの性能に強い影響を与えることが示される。
論文参考訳（メタデータ） (2021-02-08T14:55:44Z)
Ergodicity Breaking Transition in Finite Disordered Spin Chains [0.0]
我々は、相互作用するスピン-1/2鎖の高エネルギー固有状態における障害誘起エルゴディニティ破壊遷移について研究した。恒常的に、(無限次)コステリッツ-チューレス遷移は有限次遷移と比較して低いコスト関数をもたらす。
論文参考訳（メタデータ） (2020-04-03T18:00:02Z)
Hyperbolic Minesweeper is in P [0.45687771576879593]
我々は、MinesweeperがNP完全であるのに対して、その双曲的変種はPであることを示す。我々の証明はマインズウィーパーの規則に依存しないが、双曲平面に埋め込まれたグラフ上の局所的制約を満たすことに基づく任意のパズルに対して有効である。
論文参考訳（メタデータ） (2020-02-21T20:05:04Z)
On Layer Normalization in the Transformer Architecture [112.40350994368741]
まず,学習速度のウォームアップが重要である理由を理論的に検討し,レイヤー正規化の位置が重要であることを示す。ウォームアップステージのないPre-LNトランスフォーマーはベースラインと同等の結果が得られることを示す。
論文参考訳（メタデータ） (2020-02-12T00:33:03Z)

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