論文の概要: 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-11-06 23:15:03.729324
- Title: NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
- Title（参考訳）: ゼイガーのNP完全性とゼロ知識証明
- Authors: Suthee Ruangwises,
- Abstract要約: 与えられたゼーガーパズルの可解性を決定することは、非等値な正の3SAT問題からの還元によってNP完全であることが証明される。
また,Zeigerの物理ゼロ知識証明プロトコルを構築することで,証明者がパズルの解の存在を物理的に示すことができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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の物理ゼロ知識証明プロトコルを構築することで,証明者がパズルの解の存在を物理的に示すことができる。
関連論文リスト
- Characterization of the multiplicity of solutions for camera pose given two vertically-aligned landmarks and accelerometer [55.2480439325792]
2つのラベル付きランドマークのセンサ画像から加速度センサを備えたカメラの位置と向きを復元する問題を考察する。
これは、重力データなしでカメラの位置と向きを$n$ポイントから回復する、これまで研究されてきたP$n$P問題における変種である。
論文 参考訳（メタデータ） (2024-10-23T16:12:03Z) - Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles [14.777731830394357]
本研究では,因果言語モデリングが,数独パズルの解法などの複雑な課題を学習できるかどうかを考察する。
この合成タスクで訓練されたトランスフォーマーモデルが実際にスドクスの解法を学習できることが示される。
また、分析結果をZebraパズル(アインシュタインパズルとして知られる)に拡張し、モデルが92.04 %のパズルを完全に正しく解いていることを示す。
論文 参考訳（メタデータ） (2024-09-16T17:42:15Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Printing Protocol: Physical ZKPs for Decomposition Puzzles [0.4604003661048266]
我々は,デコンポジトンパズルの解の検証に使用できる,印刷プロトコルと呼ばれる汎用カードベースのプロトコルを構築した。
本稿では,カードベースのゼロ知識証明プロトコルを開発するために,印刷プロトコルを適用した。
論文 参考訳（メタデータ） (2023-02-02T17:16:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。