English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Some 25 years ago Valiant introduced an algebraic model of computation inorder to study the complexity of evaluating families of polynomials. The theorywas introduced along with the complexity classes VP and VNP which are analoguesof the classical classes P and NP. Families of polynomials that are difficultto evaluate (that is, VNP-complete) includes the permanent and hamiltonianpolynomials. In a previous paper the authors together with P. Koiran studiedthe expressive power of permanent and hamiltonian polynomials of matrices ofbounded treewidth, as well as the expressive power of perfect matchings ofplanar graphs. It was established that the permanent and hamiltonianpolynomials of matrices of bounded treewidth are equivalent to arithmeticformulas. Also, the sum of weights of perfect matchings of planar graphs wasshown to be equivalent to (weakly) skew circuits. In this paper we continue theresearch in the direction described above, and study the expressive power ofpermanents, hamiltonians and perfect matchings of matrices that have boundedpathwidth or bounded cliquewidth. In particular, we prove that permanents,hamiltonians and perfect matchings of matrices that have bounded pathwidthexpress exactly arithmetic formulas. This is an improvement of our previousresult for matrices of bounded treewidth. Also, for matrices of boundedweighted cliquewidth we show membership in VP for these polynomials.

On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth