论文标题
在无选的多项式时间中的有限和二面色类别的典范
Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time
论文作者
论文摘要
为了寻求逻辑捕获ptime的逻辑，要考虑的下一个自然类别的结构是有界颜色类尺寸的逻辑类别。我们为无界多项式时间（CPT）的二面色颜色类别的图形提供了一个典型的图形，然后在此类别的结构上捕获ptime。这是该表格的第一个结果，用于非亚洲颜色类别。第一步提出了一个正常形式，该形式包括“刚性组合”。这大致意味着局部自动形态组形成了2个注射3因子亚第6级产品。具有有界尺寸的颜色类别的结构可以在CPT中将其缩小为正常形式。在第二步中，我们表明，对于具有有限尺寸的二面颜色类别的正常形式的图形，可以在CPT中解决典范问题。如果在奇数域上定义了二面群，我们还以正常形式显示了常规三元结构的相同陈述。
In the quest for a logic capturing PTime the next natural classes of structures to consider are those with bounded color class size. We present a canonization procedure for graphs with dihedral color classes of bounded size in the logic of Choiceless Polynomial Time (CPT), which then captures PTime on this class of structures. This is the first result of this form for non-abelian color classes. The first step proposes a normal form which comprises a "rigid assemblage". This roughly means that the local automorphism groups form 2-injective 3-factor subdirect products. Structures with color classes of bounded size can be reduced canonization preservingly to normal form in CPT. In the second step, we show that for graphs in normal form with dihedral color classes of bounded size, the canonization problem can be solved in CPT. We also show the same statement for general ternary structures in normal form if the dihedral groups are defined over odd domains.
