On hardness of computing analytic Brouwer degree

07/17/2023
by   Somnath Chakraborty, et al.
0

We prove that counting the analytic Brouwer degree of rational coefficient polynomial maps in Map(ℂ^d, ℂ^d) – presented in degree-coefficient form – is hard for the complexity class ♯ P, in the following sense: if there is a randomized polynomial time algorithm that counts the Brouwer degree correctly for a good fraction of all input instances (with coefficients of bounded height where the bound is an input to the algorithm), then P^♯ P =BPP.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset