scientific article; zbMATH DE number 15994

MaRDI QIDQ3972641zbMATH OpenFDO

Authors D. J. A. Welsh

Publication date 25 June 1992

zbMATH Keywords

computational complexityenumeration problemsmonomer-dimer problempercolationrandomized approximation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

[For the entire collection see Zbl 0714.00019.] The author reviews results on the difficulty of some combinatorial problems in statistical physics (e.g. percolation, Ising model). They are based on an extension of the notion of computational complexity to enumeration problems. All these problems are \(\sharp P\)-hard or \(\sharp P\)-complete, indicating their intractability. The author also mentions the randomised approximation of Jerrum and Sinclair of the monomer-dimer problem and discusses the fact, that despite their enumeration complexity some 2-dimensional problems are exactly solvable.

Recommendations

• Percolation and the random cluster model: Combinatorial and algorithmic problems
• A Computational Proof of Complexity of Some Restricted Counting Problems
• A computational proof of complexity of some restricted counting problems

Cited in

(23)

• The computational complexity of knot and matroid polynomials
• Computational complexity of loss networks
• Approximating the number of monomer-dimer coverings of a lattice.
• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• On the number of Eulerian orientations of a graph
• The computational complexity of generating random fractals
• Statistical complexity and classical-quantum frontier
• Propriety conditions for the Bayesian autologistic model-inference for histone modifications
• The hierarchical parity model
• A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
• Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• scientific article; zbMATH DE number 5953237 (Why is no real title available?)
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Eulerian digraphs and toric Calabi-Yau varieties
• Matrix permanent and quantum entanglement of permutation invariant states
• A strong log-concavity property for measures on Boolean algebras
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)
• Counting over non-planar graphs
• Algorithmic information and simplicity in statistical physics
• Dominic Welsh: his work and influence
• Cumulant expansion for counting Eulerian orientations
• On the unimodality of the independent set numbers of a class of matroids

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972641)