計算複雑性理論

計算複雑性理論

ZKPを理解するには、計算複雑性理論を理解しなければならない。

具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。

複雑性	多項式時間計算	多項式時間検証
Polynomial Time (P)	可能	可能
Non-Deterministic Polynomial TIme (NP)	不可能	可能
PSPACE	不可能	不可能