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$