On the Complexity of Holant Problems

Authors Heng Guo, Pinyan Lu



PDF
Thumbnail PDF

File

DFU.Vol7.15301.159.pdf
  • Filesize: 0.57 MB
  • 19 pages

Document Identifiers

Author Details

Heng Guo
Pinyan Lu

Cite AsGet BibTex

Heng Guo and Pinyan Lu. On the Complexity of Holant Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 159-177, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/DFU.Vol7.15301.159

Abstract

In this article we survey recent developments on the complexity of Holant problems. We discuss three different aspects of Holant problems: the decision version, exact counting, and approximate counting.
Keywords
  • Computational complexity
  • Counting complexity
  • Dichotomy theorems
  • Approximate counting
  • Holant problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail