A Systematic Study of Single-Anchor Logical Gadgets
Fikret H. Güngör
我们提出了一个在单个锚约束下进行3种颜色的逻辑小工具的系统研究,其中只有一个代表逻辑谬误的颜色被固定在顶点上。 我们引入了一个框架,我们称之为ladgets(逻辑小工具),实现布尔函数的图形小工具。 然后,我们定义了一组核心小工具,称为原语,它有助于识别和分析ladgets的逻辑行为。 接下来,我们检查几个标准ladget的结构,并呈现适用于所有ladgets的结构约束。 通过对所有非异构连接图形的详尽搜索,多达10个顶点,我们验证了标准桂花的所有最小结构。 值得注意的是,我们在大约290亿个小工具配置中准确地识别了两个非同态最小XNOR ladget,突出了能够表达逻辑行为的图形的稀有性。 我们还介绍了一种一般的嵌入技术,将3色中的ladget嵌入到k着色中。 我们的工作展示了单锚约束如何创建一个与SAT削减中使用的两个锚点小工具完全不同的框架。
We present a systematic study of logical gadgets for 3-coloring under a single anchor constraint, where only one color representing logical falsehood is fixed to a vertex. We introduce a framework of what we call ladgets (logical gadgets), graph gadgets that implement Boolean functions. Then, we define a set of core gadgets, called primitives, which help identify and analyze the logical behavior of ladgets. Next, we examine the structure of several standard ladgets and present structural constra...