摘要翻译：
所有的布尔子模函数能否在一个可能更大的变量集上分解成一个二元子模函数的和，以前是一个公开的问题。这个问题已经在计算机科学的几个不同的背景下被考虑，包括计算机视觉、人工智能和伪布尔优化。利用值约束的表达能力和函数的某些代数性质之间的联系，我们否定地回答了这个问题。我们的结果有几个推论。首先，我们精确地刻画了哪些子模函数可以用二元子模函数表示。其次，我们确定了一类新的任意点的子模函数，它们可以用二进制子模函数表示，因此，利用所谓的最小割问题的可表达性约简有效地使其最小化。更重要的是，我们的结果暗示了这种约简的局限性，并首次证明了它不能用于任意子模函数的最小化。最后，我们驳斥了Promislow和Young关于布尔次模函数锥极射线结构的一个猜想。
---
英文标题：
《The Expressive Power of Binary Submodular Functions》
---
作者：
Stanislav Zivny, David A. Cohen, Peter G. Jeavons
---
最新提交年份：
2008
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Discrete Mathematics        离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Vision and Pattern Recognition        计算机视觉与模式识别
分类描述：Covers image processing, computer vision, pattern recognition, and scene understanding. Roughly includes material in ACM Subject Classes I.2.10, I.4, and I.5.
涵盖图像处理、计算机视觉、模式识别和场景理解。大致包括ACM课程I.2.10、I.4和I.5中的材料。
--

---
英文摘要：
  It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively.   Our results have several corollaries. First, we characterise precisely which submodular functions of arity 4 can be expressed by binary submodular functions. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.
---
PDF链接：
https://arxiv.org/pdf/0811.1885