JP ZK Learning Club
  • 貢献について
  • 前提知識
    • 暗号学
      • 決定問題
      • P/NP問題
      • 計算複雑性理論
    • 数学
      • 代数的構造
      • 離散対数問題 (DLP)
      • 楕円曲線
      • 算術回路
  • PSE-Core-Program
    • Week 1
    • Week 2 さらなる暗号技術とSNARKsとSTARKs
    • Week 5 Frontier
  • zkSNARKs
    • Spartan
  • Folding Scheme
    • Nova
    • SuperNova
    • HyperNova
    • NeutronNova
    • CycleFold
  • Lookup Argument
    • 概要とLasso以前の提案
    • Lasso
  • zkVM
    • Backgrounds
      • Multi Linear extension(MLE)
      • Folding scheme
      • Lookup Singularity
      • Cycle of Curves
      • Extension Field
      • Glossary
      • CCS
      • Switch-board (Nebula)
    • Building Blocks
      • Binius
      • GKR
      • Circle STARK
      • Sum-check Protocol
    • 動作概要
    • ゼロ知識証明
      • メモリ読み込み・書き込みの一貫性
        • Merkle-Tree
        • Spice
        • Jolt-Memory-Checking
        • Nebula
        • Proof-for-Deep-Though
      • 命令の実行
      • バイトコードから命令へのデコード
    • プロジェクト
      • SP1
      • RISC-Zero
      • Jolt
      • Valida
      • Nexus
Powered by GitBook
On this page
  1. 前提知識
  2. 暗号学

計算複雑性理論

計算複雑性理論

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

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

複雑性
多項式時間計算
多項式時間検証

Polynomial Time (P)

可能

可能

Non-Deterministic Polynomial TIme (NP)

不可能

可能

PSPACE

不可能

不可能

PreviousP/NP問題Next数学

Last updated 6 months ago