The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.

The related problem of noncommutative rational identity testing (NCIT) is known to have a deterministic polynomial algorithm.

I've seen many algorithmic applications of PIT, that work by reducing the detection of some combinatorial object (e.g. existence of a Hamiltonian cycle in a graph) to the verification that a polynomial corresponding to that object is nonzero.

Are there any analogous algorithmic applications of NCIT?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.