5
$\begingroup$

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?

$\endgroup$

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.