|
|
|
|
|
|
by brchr
3202 days ago
|
|
|
One of the key results on the role of randomness in polynomial identity testing is what's called the Schwartz–Zippel lemma.[1] As the wiki article states, "Currently, there is no known sub-exponential time algorithm that can solve this problem deterministically. However, there are randomized polynomial algorithms for testing polynomial identities." [1]https://en.wikipedia.org/wiki/Schwartz–Zippel_lemma (Note that this is in the context specifically of polynomial function equivalence.) |
|
|