決定問題

決定問題

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

決定問題は、答えが「はい」か「いいえ」になる問題を指します。

決定問題ではない問題は、ゼロ知識証明の対象になりません。

決定問題例	分類	複雑性
33は素数ですか？	素数判定問題	P
辺の長さが3, 4, 5の三角形は直角三角形ですか？	幾何学問題	P
377の素因数は13と29ですか？	素因数分解問題	NP
$A \land \lnot B$の命題論理式に対して、 $A=True, B=False$は命題論理式を満たしますか？	充足可能性問題 (SAT)	NP
$A\cdot(1-B)=1$の算術回路に対して、 $A=1, B= 1$は算術回路を満たしますか？	算術回路充足可能性問題(CircuitSAT, CSAT)	NP
$3^x \equiv 13 \pmod{17}$に対して、$x=4$は数式の解ですか？	離散対数問題 (DLP)	NP
$E: y^2 = x^3 + 7$ を有限体 $\mathbb{F}_{17}$上の楕円曲線とした時、$P =(4,10),Q=(12, 16), k=14$$k=14$は$Q = kP$を満たしますか？	楕円曲線離散対数問題(ECDLP)	NP
囲碁で次の石をD16に置くことは最善手ですか？	囲碁最適手問題	PSPACE

決定問題ではない例

1. 今日の夜ご飯何にしようか