• <option id="cacee"><noscript id="cacee"></noscript></option>
  • <table id="cacee"><noscript id="cacee"></noscript></table>
  • <td id="cacee"></td>
  • <option id="cacee"></option>
  • <table id="cacee"></table>
  • <option id="cacee"><option id="cacee"></option></option>
  • <table id="cacee"><source id="cacee"></source></table><td id="cacee"><rt id="cacee"></rt></td>
    <option id="cacee"><option id="cacee"></option></option>
     找回密碼
     立即注冊

    掃一掃,登錄網站

    首頁 百科 查看內容
    • 15907
    • 0
    • 分享到

    學術向 | 深入淺出zkSNARKs

    2019-2-9 16:14

    來源: 格密鏈

    還原示例


    為了弄明白這樣一個還原的方法,讓我們先考慮評估多項式的問題。首先,讓我們定義一個由整數常量,變量,加法,減法,乘法和(正確匹配的)括號構成的多項式(類似于布爾函數)。現在讓我們考慮下面的問題: 如果 f 是一個變量都來自于集合 {0, 1} 的多項式,并且其中包含一個零項,那么 PolyZero(f) := 1 現在我們就可以構建出一個從 SAT 到 PolyZero 的還原方法了,同時這也說明了 PolyZero 也是一個 NP 完全問題(驗證它是否屬于 NP 就作為留給你們的練習)。

    在一個布爾函數的結構要素上是可以定義一個還原函數 r 的。對于任何布爾函數 f,r(f)的值擁有相同的變量個數,并且當且僅當 r(f)(a 1,..,a k)為0時f(a 1,..,a k)為真,其中true對應于1,false對應于0,并且 r(f) 只假設了來自集合 {0, 1} 的變量值 0 或者 1:

    r(x i):=(1 - x i) r(?f):=(1 - r(f)) r((f∧g)):=(1 - (1 - r(f))(1 - r(g))) r((f∨g)):= r(f)r(g) 有些人可能會假設將 r((f ∧ g)) 定義為 r(f) + r(g),但是那樣的話多項式的結果就會超出集合 {0, 1} 了。 使用函數 r,((x ∧ y) ∨?x) 被轉換成了 (1 – (1 – (1 – x))(1 – (1 – y))(1 – (1 – x))。 注意,對于 r 來說,每一個替換規則都滿足了之前聲明的目的,因此 r 也正確的實現了還原: 當且僅當r(f) 含有集合 {0, 1} 中的一個 0 時,SAT(f) = PolyZero(r(f)) 或者說 f 是可滿足的

    版權申明:本內容來自于互聯網,屬第三方匯集推薦平臺。本文的版權歸原作者所有,文章言論不代表鏈門戶的觀點,鏈門戶不承擔任何法律責任。如有侵權請聯系QQ:3341927519進行反饋。
    相關新聞
    發表評論

    請先 注冊/登錄 后參與評論

      回頂部
    • <option id="cacee"><noscript id="cacee"></noscript></option>
    • <table id="cacee"><noscript id="cacee"></noscript></table>
    • <td id="cacee"></td>
    • <option id="cacee"></option>
    • <table id="cacee"></table>
    • <option id="cacee"><option id="cacee"></option></option>
    • <table id="cacee"><source id="cacee"></source></table><td id="cacee"><rt id="cacee"></rt></td>
      <option id="cacee"><option id="cacee"></option></option>
      妖精视频