5 lines
304 B
Markdown
5 lines
304 B
Markdown
# 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`$
|