在计算机学科中，存在多项式时间算法的一类问题，称为P类问题；存在至今没有找到多项式时间算法解的一类问题（如旅行商问题、命题表达式可满足问题），称为NP类问题。

NP类问题中最难的称为NP完全问题。如旅行商问题：某推销员要从城市v1出发，访问其他城市v2，v3，…，vn各一次且仅一次，最后返回v1。D为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？

Goldreich指出每个NP问题都可以转化为可计算的交互零知识证明。这里我们不妨用“三色图（G3C）”问题进行说明。

假设被认证方希望向认证方证实某输入图是三色可见的，但不泄露他知道的颜色，他使用了下面这个协议（需要重复执行|E|2次）。

（1）被认证方随机变换三个颜色（如可以将所有红点变成蓝点，所有的蓝点变成黄点，所有的黄点变成红点）。

（2）被认证方对每个点的颜色加密（每个点使用不同的加密算法），并告诉认证方所有的加密算法以及相应的密文。

（3）认证方随机选择图的一条边。

（4）被认证方用相应的解密密钥对这条边两点的颜色的密文进行解密。

（5）认证方证实解密是正确的，这条边的两点是两种不同的颜色。

如果这个图确实是三色可见的，那么认证方将不会再检查任何未被正确标注的边。不过，如果这个图不是三色可见的，那么被认证方在每次执行协议时，至少有1/|E|的概率被发现他在欺骗认证方。在|E|2次执行过程中，被认证方不被发现他在欺骗认证方的概率是很低的。(www.daowen.com)

下面我们来证明它是零知识证明。

（1）完备性

令G∈G3C，u和v是边的两个端点，可以得到u和v是不同色的，因此，诚实的认证方会在协议执行|E|2次后接受图是三色可见的。

（2）正确性

令G∉G3C，那么G至少有一条边没有被正确着色，因此，诚实的认证方在每次协议中拒绝的可能性为1/|E|。

（3）零知识性

协议的每次执行过程中，唯一泄露的信息是π（ϕ（u））和π（ϕ（v）），其中u和v是边的两个端点，π是随机选择的边。这样输出结果便是不可计算的，被认证方在交互过程中不会泄露边的颜色的任何信息。

这个例子很好地说明了零知识证明在NP问题中的应用，不难发现，每一个NP问题都存在这样一个零知识证明。