Jānis Iraids ; Juris Smotrovs - Representing polynomial of ST-CONNECTIVITY

dmtcs:9934 - Discrete Mathematics & Theoretical Computer Science, April 29, 2024, vol. 25:2 - https://doi.org/10.46298/dmtcs.9934
Representing polynomial of ST-CONNECTIVITYArticle

Authors: Jānis Iraids ; Juris Smotrovs

    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^{\Omega(n^2)}$.


    Volume: vol. 25:2
    Section: Combinatorics
    Published on: April 29, 2024
    Accepted on: October 19, 2023
    Submitted on: August 18, 2022
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity,05C40, 06B99,G.2.2

    Consultation statistics

    This page has been seen 164 times.
    This article's PDF has been downloaded 63 times.