论文部分内容阅读
复杂性理论是计算机理论的一个重要分支。而计数问题又是时间复杂性理论中的一类关键问题。本文的主要研究集中于计数问题的多项式时间算法。而全息算法作为一个新兴算法为我们提供了全新的判定计数问题的方法。并给出了构造匹配门来实现标识的思想。Holant问题是研究计数问题应用最广泛的框架，且给出了对称标识情况下的完整的二分定理。本文基于以上研究，通过多项式插值、全息归约和构件设计的方法研究并给出了在非对称情况下，三元布尔标识的二分定理。为非对称标识的研究提供了理论基础。之后给出了一系列应用全息算法和Holant问题来解决计数问题的实例，并分析了两种算法的优缺点。