发帖
雷达卡
摘要翻译：
约束满足问题的保守类CSPs是在任意域约简下保持隶属度的一类。许多众所周知的可处理的CSPs类都是保守的。众所周知，lexleader约束可以通过排除CSP的对称解而显著减少解的数量。我们证明了在任何保守的CSPs类的任何实例中添加某些lexleader约束仍然允许我们在连续解之间的时间为多项式的情况下找到所有解。时间是实例的总大小和附加的lexleader约束的多项式。众所周知，对于完全的对称性破缺，可能需要指数数量的lexleader约束。但是，在实践中，附加的lexleader约束的数量通常是实例大小的多项式数。对于多项式的多个lexleader约束，我们通常可能没有完全的对称破缺，但多项式的多个lexleader约束可能提供实际有用的对称破缺--它们有时排除超指数的多个解。我们证明了对于保守类中的任何一个实例，即使在没有LexLeaderConstraints的情况下，在具有多项式多个附加LexLeaderConstraints的情况下，求连续解之间的时间也是多项式的。
---
英文标题：
《Symmetry Breaking with Polynomial Delay》
---
作者：
Tim januschowski and Barbara M. Smith and M. R. C. van Dongen
---
最新提交年份：
2010
---
分类信息：
一级分类：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中的材料。
--
---
英文摘要：
A conservative class of constraint satisfaction problems CSPs is a class for which membership is preserved under arbitrary domain reductions. Many well-known tractable classes of CSPs are conservative. It is well known that lexleader constraints may significantly reduce the number of solutions by excluding symmetric solutions of CSPs. We show that adding certain lexleader constraints to any instance of any conservative class of CSPs still allows us to find all solutions with a time which is polynomial between successive solutions. The time is polynomial in the total size of the instance and the additional lexleader constraints. It is well known that for complete symmetry breaking one may need an exponential number of lexleader constraints. However, in practice, the number of additional lexleader constraints is typically polynomial number in the size of the instance. For polynomially many lexleader constraints, we may in general not have complete symmetry breaking but polynomially many lexleader constraints may provide practically useful symmetry breaking -- and they sometimes exclude super-exponentially many solutions. We prove that for any instance from a conservative class, the time between finding successive solutions of the instance with polynomially many additional lexleader constraints is polynomial even in the size of the instance without lexleaderconstraints.
---
PDF链接：
https://arxiv.org/pdf/1012.5585
京公网安备 11010802022788号
