Connectivity in Symmetric Semi-Algebraic Sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914833008427008 |
|---|---|
| author | Riener, Cordian Schabert, Robin Vu, Thi Xuan |
| author_facet | Riener, Cordian Schabert, Robin Vu, Thi Xuan |
| contents | Semi-algebraic set is a subset of the real space defined by polynomial equations and inequalities. In this paper, we consider the problem of deciding whether two given points in a semi-algebraic set are connected. We restrict to the case when all equations and inequalities are invariant under the action of the symmetric group and their degrees at most $d<n$, where $n$ is the number of variables. Additionally, we assume that the two points are in the same fundamental domain of the action of the symmetric group, by assuming that the coordinates of two given points are sorted in non-decreasing order. We construct and analyze an algorithm that solves this problem, by taking advantage of the group action, and has a complexity being polynomial in $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Connectivity in Symmetric Semi-Algebraic Sets Riener, Cordian Schabert, Robin Vu, Thi Xuan Symbolic Computation Semi-algebraic set is a subset of the real space defined by polynomial equations and inequalities. In this paper, we consider the problem of deciding whether two given points in a semi-algebraic set are connected. We restrict to the case when all equations and inequalities are invariant under the action of the symmetric group and their degrees at most $d<n$, where $n$ is the number of variables. Additionally, we assume that the two points are in the same fundamental domain of the action of the symmetric group, by assuming that the coordinates of two given points are sorted in non-decreasing order. We construct and analyze an algorithm that solves this problem, by taking advantage of the group action, and has a complexity being polynomial in $n$. |
| title | Connectivity in Symmetric Semi-Algebraic Sets |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2404.09749 |