In this work we advance the understanding of the fundamental limits of computation for Binary Polynomial Optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a vast novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whose corresponding hypergraph is $\beta$-acyclic. We note that the $\beta$-acyclicity assumption is natural in several applications including relational database schemes and the lifted multicut problem on trees. Due to the novelty of our proving technique, we obtain an algorithm which is interesting also from a practical viewpoint. This is because our algorithm is very simple to implement and the running time is a polynomial of very low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs, since the problem is NP-hard on $\alpha$-acyclic instances. Our algorithm can also be applied to any general BPO problem that contains $\beta$-cycles. For these problems, the algorithm returns a smaller instance together with a rule to extend any optimal solution of the smaller instance to an optimal solution of the original instance.

翻译：在这项工作中,我们增进了对二元多元优化计算基本限值的理解,这是在所有二元点上最大限度地实现给定多元值功能的问题。 在主要结果中,我们提供了庞大的新颖的BPO类,从理论和计算角度都能有效解决。事实上,我们给相应的高压值为$\beta$-周期的事例提供了强烈的多元时间算法。我们注意到,$\bea$-周期性假设在一些应用中是自然的,包括关系数据库计划和树上已消除的多截面问题。由于我们论证技术的新颖性,我们获得了一种也从实用角度有趣的算法。这是因为我们的算法非常简单,运行时间是高压值和边缘数非常低的多元数。我们的结果完全解决了BPO对周期性高压值的计算复杂性,因为问题在$\alpha$-a-cal-cople 树上是硬的问题。由于我们的论证技术创新技术,我们获得了一种也从实用角度引人兴趣的算法。这是因为我们的算法过程非常简单、最优的算法也是一种最优的版本。我们最优的解法的返回。