Representing polynomial of ST-CONNECTIVITY
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929449876848640 |
|---|---|
| author | Iraids, Jānis Smotrovs, Juris |
| author_facet | Iraids, Jānis Smotrovs, Juris |
| contents | We show that the coefficients of the representing polynomial of any monotone Boolean function are the values of the Möbius function of an atomistic lattice related to this function. Using this we determine the representing polynomial of any Boolean function corresponding to a ST-CONNECTIVITY problem in acyclic quivers (directed acyclic multigraphs). Only monomials corresponding to unions of paths have non-zero coefficients which are $(-1)^D$ where $D$ is an easily computable function of the quiver corresponding to the monomial (it is the number of plane regions in the case of planar graphs). We determine that the number of monomials with non-zero coefficients for the two-dimensional $n \times n$ grid connectivity problem is $2^{Ω(n^2)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_15018 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Representing polynomial of ST-CONNECTIVITY Iraids, Jānis Smotrovs, Juris Discrete Mathematics Computational Complexity 05C40, 06B99 G.2.2 We show that the coefficients of the representing polynomial of any monotone Boolean function are the values of the Möbius function of an atomistic lattice related to this function. Using this we determine the representing polynomial of any Boolean function corresponding to a ST-CONNECTIVITY problem in acyclic quivers (directed acyclic multigraphs). Only monomials corresponding to unions of paths have non-zero coefficients which are $(-1)^D$ where $D$ is an easily computable function of the quiver corresponding to the monomial (it is the number of plane regions in the case of planar graphs). We determine that the number of monomials with non-zero coefficients for the two-dimensional $n \times n$ grid connectivity problem is $2^{Ω(n^2)}$. |
| title | Representing polynomial of ST-CONNECTIVITY |
| topic | Discrete Mathematics Computational Complexity 05C40, 06B99 G.2.2 |
| url | https://arxiv.org/abs/2106.15018 |