論文の概要: NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
- arxiv url: http://arxiv.org/abs/2409.14308v1
- Date: Sun, 22 Sep 2024 04:25:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-09-26 02:48:17.603277
- Title: NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
- Title(参考訳): ゼイガーのNP完全性とゼロ知識証明
- Authors: Suthee Ruangwises,
- Abstract要約: 与えられたゼーガーパズルの可解性を決定することは、非等値な正の3SAT問題からの還元によってNP完全であることが証明される。
また,Zeigerの物理ゼロ知識証明プロトコルを構築することで,証明者がパズルの解の存在を物理的に示すことができる。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: Zeiger is a pencil puzzle consisting of a rectangular grid, with each cell having an arrow pointing in horizontal or vertical direction. Some cells also contain a positive integer. The objective of this puzzle is to fill a positive integer into every unnumbered cell such that the integer in each cell is equal to the number of different integers in all cells along the direction an arrow in that cell points to. In this paper, we prove that deciding solvability of a given Zeiger puzzle is NP-complete via a reduction from the not-all-equal positive 3SAT (NAE3SAT+) problem. We also construct a card-based physical zero-knowledge proof protocol for Zeiger, which enables a prover to physically show a verifier the existence of the puzzle's solution without revealing it.
- Abstract(参考訳): ゼーガー(Zeiger)は、長方形格子からなる鉛筆パズルで、各セルが水平方向または垂直方向に矢印を向けている。
一部の細胞は正の整数も含む。
このパズルの目的は、正の整数を、各セルの整数が、そのセルの矢印が指している方向に沿った全てのセルの異なる整数の数に等しいように、すべての無数のセルに埋めることである。
本稿では,Zeiger パズルの解答性を決定することは,非等値な正の 3SAT (NAE3SAT+) 問題から還元することで NP 完全であることが証明される。
また,Zeigerの物理ゼロ知識証明プロトコルを構築することで,証明者がパズルの解の存在を物理的に示すことができる。
関連論文リスト
- Almost All Quantum Channels Are Diagonalizable [0.0]
我々は「単純な固有値しか持たない$mathcal S$のすべての要素の集まりは$mathcal S$で密接である」という文を証明している。
論文 参考訳(メタデータ) (2024-03-28T17:54:33Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - Permutation Invariant Representations with Applications to Graph Deep
Learning [8.403227482145297]
本稿では、任意の任意の列列置換が与えられた行列によって生成される商空間のユークリッド埋め込みについて述べる。
ほぼ至るところで、最小冗長性と計算コストの低いインジェクティブスキームを実装できる。
論文 参考訳(メタデータ) (2022-03-14T23:13:59Z) - Constructing Approximately Diagonal Quantum Gates [0.0]
ほぼ対角 1-qubit ゲートの製作法について検討する。
各正の整数に対して、固定対角ゲートと任意のゲートから反復的に定義されるゲートの列を提供する。
これらの列は2倍に指数関数的に高速な対角ゲートに収束すると予想され、小さな整数に対して検証される。
論文 参考訳(メタデータ) (2021-09-10T23:40:24Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳(メタデータ) (2021-08-10T15:00:20Z) - A new perspective of paramodulation complexity by solving massive 8
puzzles [0.4514386953429769]
スライディングパズルは、プレイヤーがボード上の特定のルートに沿ってスライドして特定のエンド構成に達するコンビネーションパズルです。
パラモジュレーションで得られる節数をカウントすることで、各パズルの難易度を評価できることが分かりました。
論文 参考訳(メタデータ) (2020-12-15T11:47:47Z) - Generating Correct Answers for Progressive Matrices Intelligence Tests [88.78821060331582]
Ravenのプログレッシブマトリクス(Progressive Matrices)は、複数選択のインテリジェンステストである。
このテストに対処する以前の試みは、複数の選択肢の中から正しい回答を選択することに集中していました。
この作業では、代わりに、定義によって難しいタスクである選択を見ることなく、グリッドに与えられた正しい回答を生成することに焦点を合わせます。
論文 参考訳(メタデータ) (2020-11-01T13:21:07Z) - Decomposable Pauli diagonal maps and Tensor Squares of Qubit Maps [91.3755431537592]
キュービット写像の任意の正積がそれ自身で分解可能であることを示す。
分解可能な四角形パウリ対角写像の錐を特徴づける。
論文 参考訳(メタデータ) (2020-06-25T16:39:32Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳(メタデータ) (2019-09-04T11:46:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。