Formal definition of NP

It is traditional to view NP as the class of languages whose elements posses short proofs of membership. A “proof that z∈ L ” is a witness w_z such that P_L(z,w_z)=l,where P_L is a polynomial-time computable Boolean predicate associated to the language L such t hat P_L(z, y)=0 for all y if z is not in L . The witness must have length polynomial in the length of the input z , but needs not be computable from x in polynomial time. A slightly different point of view is to consider NP as the class of languages L for which a powerful prover may prove membership in L to polynomial-time deterministic verifiers. The interaction between the prover and the verifier, in this case, is trivial: the prover sends a witness (“proof”) and the verifier computes for polynomial time to verify
that it is indeed a proof.

NPは、要素がメンバーシップの証明を簡潔に持つ言語のクラスとして捉えるのが一般的です。「z∈Lの証明」とは、P_L(z,w_z)=lとなるような証拠w_zのことです。ここで、P_Lは言語Lに関連付けられた多項式時間で計算可能なブール述語であり、zがLに含まれない場合、すべてのyに対してP_L(z,y)=0となります。証拠の長さは入力zの長さの多項式である必要がありますが、xから多項式時間で計算可能である必要はありません。少し異なる視点としては、NPを、強力な証明者が多項式時間で決定論的な検証者に対してLへのメンバーシップを証明できる言語Lのクラスと考える方法があります。この場合、証明者と検証者の間のやり取りは単純です。証明者は証拠（「証明」）を送信し、検証者は多項式時間で計算して、それが確かに証明であることを検証します。

https://scispace.com/pdf/how-to-prove-all-np-statements-in-zero-knowledge-and-a-4l3wxo6n8y.pdf