決定問題

ZKPの勉強に対して一番理解が必要な部分は決定問題になります。

決定問題は、答えが「はい」か「いいえ」になる問題を指します。
決定問題ではない問題は、ゼロ知識証明の対象になりません。

決定問題例

分類

複雑性

33は素数ですか？

素数判定問題

辺の長さが3, 4, 5の三角形は直角三角形ですか？

幾何学問題

377の素因数は13と29ですか？

素因数分解問題

$A \land \lnot B$ の命題論理式に対して、

$A=True, B=False$ は命題論理式を満たしますか？

$A\cdot(1-B)=1$ の算術回路に対して、

$A=1, B= 1$ は算術回路を満たしますか？

算術回路充足可能性問題(CircuitSAT, CSAT)

$3^x \equiv 13 \pmod{17}$ に対して、 $x=4$ は数式の解ですか？

離散対数問題 (DLP)

$E: y^2 = x^3 + 7$ を有限体 $\mathbb{F}_{17}$ 上の楕円曲線とした時、 $P =(4,10),Q=(12, 16), k=14$ $k=14$ は $Q = kP$ を満たしますか？

楕円曲線離散対数問題(ECDLP)

囲碁で次の石をD16に置くことは最善手ですか？

囲碁最適手問題

PSPACE

決定問題ではない例

Last updated 9 months ago