Scholarlink

On the Boolean domain, there is a class of symmetric signatures called “Fibonacci gates” for which a beautiful P-time combinatorial algorithm has been designed for the corresponding \(\operatorname {Holant}\) problems. In this work, I give a combinatorial view for \(\operatorname {Holant}(\mathcal {F})\) problems on a domain of size 3 where \(\mathcal {F}\) is a set of arity 3 functions with inputs taking values on the domain of size 3 and the functions share some common properties. The combinatorial view can also be extended to the domain of size 4. Specifically, I extend the definition of “Fibonacci gates” to the domain of size 3 and the domain of size 4. Moreover, I give the corresponding combinatorial algorithms.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Combinatorial View of Holant Problems on Higher Domains

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yin Liu

摘要

On the Boolean domain, there is a class of symmetric signatures called “Fibonacci gates” for which a beautiful P-time combinatorial algorithm has been designed for the corresponding \(\operatorname {Holant}\) problems. In this work, I give a combinatorial view for \(\operatorname {Holant}(\mathcal {F})\) problems on a domain of size 3 where \(\mathcal {F}\) is a set of arity 3 functions with inputs taking values on the domain of size 3 and the functions share some common properties. The combinatorial view can also be extended to the domain of size 4. Specifically, I extend the definition of “Fibonacci gates” to the domain of size 3 and the domain of size 4. Moreover, I give the corresponding combinatorial algorithms.