garden/np.md

NP

• class of languages whose membership proofs can be verified in polynomial time
• the discrete-log problem is an example of an NP problem
  • from `g^x` in a finite field it is hard to compute `\log_g\left(g^x\right)`, but easy to check `g^x = g^y` to validate a knowledge proof of `x`