Fugu-MT 論文翻訳(概要): NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

論文の概要: NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

arxiv url: http://arxiv.org/abs/2603.01393v1
Date: Mon, 02 Mar 2026 02:43:54 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-03 19:50:56.657064
Title: NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
Title（参考訳）: ホタルビームのNP完全性とゼロ知識証明
Authors: Taisei Otsuji, Peter Fulla, Takuro Fukunaga,
Abstract要約: ホタルビーム(Hotaru Beam)は、格子上に張られた円を、特定の起点と曲がりの数だけを引いて結ぶ論理パズルである。ホタルビームはNP完全であり、物理的ゼロ知識証明を示す。
参考スコア（独自算出の注目度）: 1.9007546108571114
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge proof is a communication protocol that allows one player to persuade the other that they are in possession of a certain piece of information without actually revealing it. We show that Hotaru Beam is NP-complete and present a physical zero-knowledge proof (i.e. implementable using physical items) for proving that one knows a solution to the puzzle.
Abstract（参考訳）: ホタルビーム(Hotaru Beam)は、格子上に張られた円を、特定の起点と曲がりの数だけを引いて結ぶ論理パズルである。ゼロ・知識証明(ゼロ・知識証明、zero-knowledge proof)とは、あるプレイヤーが、ある情報を実際に公開せずに保持していることを他のプレイヤーに納得させる通信プロトコルである。本稿では,Hotaru BeamがNP完全であることを示し,パズルの解法を知っていることを証明するための物理ゼロ知識証明(物理項目を用いて実装できる)を提案する。

関連論文リスト

PuzzleWorld: A Benchmark for Multimodal, Open-Ended Reasoning in Puzzlehunts [47.92619068073141]
我々は、ステップバイステップ、オープンエンド、クリエイティブマルチモーダル推論を評価するために設計された667のパズルハントスタイルの大規模ベンチマークであるPuzzleWorldを紹介した。ほとんどの最先端モデルでは最終解の精度は1-2%に過ぎず、最高のモデルではパズルの14%しか解けず、ステップワイズ精度は40%に達する。誤り解析により,現在のモデルは筋力的推論を示し,言語に基づく推論の限界に悩まされ,視覚的および空間的推論に不可欠なスケッチ能力が欠如していることが判明した。
論文参考訳（メタデータ） (2025-06-06T16:17:09Z)
NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger [0.0]
与えられたゼーガーパズルの可解性を決定することは、非等値な正の3SAT問題からの還元によってNP完全であることが証明される。また,Zeigerの物理ゼロ知識証明プロトコルを構築することで,証明者がパズルの解の存在を物理的に示すことができる。
論文参考訳（メタデータ） (2024-09-22T04:25:13Z)
Fuse, Reason and Verify: Geometry Problem Solving with Parsed Clauses from Diagram [78.79651421493058]
平面幾何学的問題解法 (PGPS) のニューラルネットワークモデルを提案し, モーダル融合, 推論過程, 知識検証の3つの重要なステップについて述べる。推論のために、幾何学的推論過程を記述するための説明可能な解プログラムを設計し、自己限定デコーダを用いて解プログラムを自動回帰的に生成する。また, PGPS9Kと呼ばれる大規模幾何学的問題データセットを構築し, テキスト節, 解法プログラム, 関連知識解決器の詳細なアノテーションを含む。
論文参考訳（メタデータ） (2024-07-10T02:45:22Z)
The Round Complexity of Proofs in the Bounded Quantum Storage Model [0.7366405857677227]
有界量子記憶モデル(BQSM)におけるプロトコルのラウンド圧縮に関する研究このモデルでは、悪意のあるパーティは有界量子メモリを持ち、プロトコルに送信される全てのキュービットを格納できない。標準手法では, NIZKはBQS相手に対する平易なモデルではありそうにないことを示す。
論文参考訳（メタデータ） (2024-05-28T15:24:48Z)
Unclonable Non-Interactive Zero-Knowledge [11.013799869152132]
非対話的ZK(NIZK)証明は、秘密を明かさずにNPステートメントの検証を可能にする。本稿では,クローン化が不可能なNIZK証明システムを構築するために,量子情報に頼ることが可能かどうかを問う。
論文参考訳（メタデータ） (2023-10-11T01:32:36Z)
Point Cloud Completion Guided by Prior Knowledge via Causal Inference [19.935868881427226]
本稿では,ポイントPCと呼ばれる新たなクラウド完了タスクを提案する。 Point-PCはメモリネットワークを用いて形状の先行情報を検索し、因果推論モデルを設計し、欠落した形状情報をフィルタリングする。 ShapeNet-55、PCN、KITTIデータセットの実験結果から、Point-PCは最先端の手法よりも優れていることが示された。
論文参考訳（メタデータ） (2023-05-28T16:33:35Z)
Printing Protocol: Physical ZKPs for Decomposition Puzzles [0.4604003661048266]
我々は,デコンポジトンパズルの解の検証に使用できる,印刷プロトコルと呼ばれる汎用カードベースのプロトコルを構築した。本稿では,カードベースのゼロ知識証明プロトコルを開発するために,印刷プロトコルを適用した。
論文参考訳（メタデータ） (2023-02-02T17:16:32Z)
Neural Correspondence Field for Object Pose Estimation [67.96767010122633]
1枚のRGB画像から3次元モデルで剛体物体の6DoFポーズを推定する手法を提案する。入力画像の画素で3次元オブジェクト座標を予測する古典的対応法とは異なり,提案手法はカメラフラストラムでサンプリングされた3次元クエリポイントで3次元オブジェクト座標を予測する。
論文参考訳（メタデータ） (2022-07-30T01:48:23Z)
Exploiting Reasoning Chains for Multi-hop Science Question Answering [51.86289192292466]
我々のフレームワークは、コーパス固有のアノテーションを必要とせずに説明可能な推論を行うことができる。ローカルチェーン情報とグローバルチェーン情報の両方に関するTextitChain対応の損失は、生成されたチェーンが遠隔監視信号として機能するようにも設計されている。
論文参考訳（メタデータ） (2021-09-07T07:22:07Z)
Single-photon nonlocality in quantum networks [55.41644538483948]
単一光子の絡み合った状態の非局所性は、それでもビームスプリッタと光検出器のみからなる量子ネットワークにおいて明らかにできることを示す。この結果から,単光子絡み合いはベルベースの量子情報プロトコルに有用な真のネットワーク非局所相関を生成するための有望な解となる可能性が示唆された。
論文参考訳（メタデータ） (2021-08-03T20:13:24Z)
PMP-Net: Point Cloud Completion by Learning Multi-step Point Moving Paths [54.459879603473034]
我々はPMP-Netと呼ばれる新しいニューラルネットワークを設計し、地球移動体の動作を模倣する。不完全な入力の各点を移動させ、ポイントクラウドを完結させ、ポイント移動パスの合計距離が最も短くなる。点レベルの厳密でユニークな対応を学習し、不完全な形状と完全なターゲットの間の詳細なトポロジーと構造的関係を捉えることができる。
論文参考訳（メタデータ） (2020-12-07T01:34:38Z)
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
論文参考訳（メタデータ） (2020-11-05T05:40:05Z)

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