NP-proofs

文档摘要

Lecture1:Introduction to Zero knowledge Interactive Proofs NP NP Proof: NP-proofs 属于可高效验证的 proofs.其中要求 1.Witness 的长度应当是 statement x 的长度的多项式表示. 2.Verifier 时间是 x 长度的多项式函数表示 NP proofs 例子上述例子都可以用一种通用的语言关系 L 来表示更具体而言,上述都是 NP 问题:(简单来说,求解困难,但是验证高效的问题) P NP NPC P 问题：指能在多项式时间求解出的问题.