對于NP類中的所有問題都是zkSNARK，實際上，現在存在的實際使用的zkSNARKs通常意義上都是NP問題。目前尚不清楚有沒有不屬于 NP 問題的 zkSNARKs 存在。
NP中的所有問題總是具有一定的結構，這源于NP的定義： NP 問題是 L（含有多項式時間的程序 V）的一類問題， 這個程序 V 可以在給定一個多項式尺度的叫做因子的 witness 的情況下驗證這個因子。更正式的說就是： 當且僅當一些多項式尺度的字符串 w（被稱作 witness）滿足 V(x, w) = 1 時，L(x) = 1 成立。 作為NP中問題的一個例子，讓我們考慮布爾公式可滿足性（SAT）的問題。為此，我們使用歸納定義定義布爾函數：
任何變量x 1，x 2，x 3，...都是布爾函數（我們還使用任何其他字符來表示變量 如果f是布爾函數，則?f是布爾函數（否命題） 如果f和g是布爾函數，那么（f∧g）和（f∨g）也是布爾函數（∧是且，∨是或）。 字符串“（（X 1 ∧X 2）∧?x 2）”也是一個布爾函數。
如果有一種方法可以將真值賦給變量，那么布爾函數是可以滿足的，這樣公式的計算結果為真（其中σ為真，?false為真，true∧false為假，依此類推）。可滿足性問題SAT是所有可滿足的布爾函數的集合。
當且僅當 f 是一個可滿足函數且不是 0 時，SAT(f) := 1 成立 上面的例子中，“（（X 1 ∧X 2）∧?x 2）”，是不符合要求的，因此它不屬于SAT。證明一個給定公式滿足定義并且同時確保它賦值的變量也是可滿足的就是一個可以在多項式時間內被解決的問題。
版權申明：本內容來自于互聯網，屬第三方匯集推薦平臺。本文的版權歸原作者所有，文章言論不代表鏈門戶的觀點，鏈門戶不承擔任何法律責任。如有侵權請聯系QQ：3341927519進行反饋。
