Fugu-MT 論文翻訳(概要): Hyperbolic Minesweeper is in P

論文の概要: Hyperbolic Minesweeper is in P

arxiv url: http://arxiv.org/abs/2002.09534v2
Date: Fri, 28 Jul 2023 21:26:04 GMT
ステータス: 処理完了
システム内更新日: 2023-08-02 18:45:38.155222
Title: Hyperbolic Minesweeper is in P
Title（参考訳）: 双曲型ミネズウィーパーはpです
Authors: Eryk Kopczy\'nski
Abstract要約: 我々は、MinesweeperがNP完全であるのに対して、その双曲的変種はPであることを示す。我々の証明はマインズウィーパーの規則に依存しないが、双曲平面に埋め込まれたグラフ上の局所的制約を満たすことに基づく任意のパズルに対して有効である。
参考スコア（独自算出の注目度）: 0.45687771576879593
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
Abstract（参考訳）: minesweeperはnp完全であるが、その双曲的変種は p であることを示している。この証明は minesweeper の規則に依存しないが、双曲的平面に埋め込まれたグラフ上の局所的な制約を満たすことで、どんなパズルに対しても有効である。

関連論文リスト

Topograph: An efficient Graph-Based Framework for Strictly Topology Preserving Image Segmentation [78.54656076915565]
位相的正しさは多くの画像分割タスクにおいて重要な役割を果たす。ほとんどのネットワークは、Diceのようなピクセル単位の損失関数を使って、トポロジカルな精度を無視して訓練されている。トポロジ的に正確な画像セグメンテーションのための新しいグラフベースのフレームワークを提案する。
論文参考訳（メタデータ） (2024-11-05T16:20:14Z)
The Complexity of Symmetry Breaking Beyond Lex-Leader [2.8733698089003745]
本稿では,SAT における完全 SBP や lex-leader などの計算の複雑さについて検討する。本研究の主な成果は,SBPを効率よく計算する上での自然な障壁,すなわちグラフ非同型性の効率的な証明である。この結果から,行列対称性を持つ行列モデルやグラフ生成問題などの重要なCP問題に対して,短いSBPを得ることの難しさが説明できる。
論文参考訳（メタデータ） (2024-07-05T11:09:55Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
Neural Network Learner for Minesweeper [0.0]
このプロジェクトでは、マインズウィーパーを解くニューラルネットワークベースの学習者を提案する。最高の学習者を選ぶために、ニューラルネットワークの異なるアーキテクチャと構成が数十万のゲームでトレーニングされた。驚くべきことに、提案したニューラルネットワークベースの学習器は、Minesweeperを解くのに非常に優れた近似関数であることが示されている。
論文参考訳（メタデータ） (2022-11-30T14:42:05Z)
Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
論文参考訳（メタデータ） (2022-10-18T15:10:25Z)
Sparse random hypergraphs: Non-backtracking spectra and community detection [10.503525445174464]
我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。これは、一般的な対称確率テンソルに従って$r$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なアルゴリズムである。
論文参考訳（メタデータ） (2022-03-14T17:45:03Z)
Fast constraint satisfaction problem and learning-based algorithm for solving Minesweeper [0.0]
現在の作品は、このゲームを制約満足問題(CSP)とマルコフ決定プロセス(MDP)としてモデル化します。 CSP ベースの Minesweeper ゲームのすべての解を高速に列挙するために、決定論的解探索 (DSScsp) を用いて独立集合から従属として命名された新しい方法を提案する。また,Minesweeperゲームにおいて,改良された深層Q-ラーニングを精度良く,多目的学習に応用するための新たな報奨手法を提案する。
論文参考訳（メタデータ） (2021-05-10T05:27:15Z)
Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文参考訳（メタデータ） (2021-05-03T16:36:27Z)
Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文参考訳（メタデータ） (2021-01-21T10:35:09Z)
A Phase Transition in Minesweeper [0.0]
ミナスウィーパーの演奏はNP完全であることが知られている。我々はマインズウィーパーがよく研究されたSAT相転移に類似した相転移を示すことを示す。
論文参考訳（メタデータ） (2020-08-10T13:21:13Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)

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