On hardness of computing analytic Brouwer degree
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915487640715264 |
|---|---|
| author | Chakraborty, Somnath |
| author_facet | Chakraborty, Somnath |
| contents | We prove that counting the analytic Brouwer degree of rational coefficient polynomial maps in $\operatorname{Map}(\mathbb C^d, \mathbb C^d)$ -- presented in degree-coefficient form -- is hard for the complexity class $\operatorname{\sharp 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 $\operatorname{P}^{\operatorname{\sharp P}} =\operatorname{BPP}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_08724 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On hardness of computing analytic Brouwer degree Chakraborty, Somnath Computational Complexity Combinatorics Probability We prove that counting the analytic Brouwer degree of rational coefficient polynomial maps in $\operatorname{Map}(\mathbb C^d, \mathbb C^d)$ -- presented in degree-coefficient form -- is hard for the complexity class $\operatorname{\sharp 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 $\operatorname{P}^{\operatorname{\sharp P}} =\operatorname{BPP}$. |
| title | On hardness of computing analytic Brouwer degree |
| topic | Computational Complexity Combinatorics Probability |
| url | https://arxiv.org/abs/2307.08724 |