top | item 37738159

(no title)

jasonmorton | 2 years ago

> Checking the work takes the same resources as doing the work. > As much as this would be wonderful in a universe where it's possible, it's simply not possible.

We do live in that universe, under some currently believed assumptions. An NP-complete problem is an example of something where checking a solution is (thought to be) easier than finding one.

Zero-knowledge proofs make it such that checking that a computation (such as inference) has been done correctly is easier than doing the computation (even keeping some parts private). A great reference is here: https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

discuss

order

No comments yet.