The Algebraic Cost of a Boolean Sum
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915395807477760 |
|---|---|
| author | Orzel, Ian Srinivasan, Srikanth Tavenas, Sébastien Yehudayoff, Amir |
| author_facet | Orzel, Ian Srinivasan, Srikanth Tavenas, Sébastien Yehudayoff, Amir |
| contents | It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the ``cost of a boolean sum," while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02442 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Algebraic Cost of a Boolean Sum Orzel, Ian Srinivasan, Srikanth Tavenas, Sébastien Yehudayoff, Amir Computational Complexity It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the ``cost of a boolean sum," while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity. |
| title | The Algebraic Cost of a Boolean Sum |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2502.02442 |