一見して、検証者が解法を知らないのに解法があるかどうかを判断するのは不可能に思われるが、npに属するあらゆる問題にはいわゆるゼロ知識証明があると信じられており、暗号理論にとって重要である。