论文标题
TP完成问题的原子观点
An Atomic Viewpoint of the TP Completion Problem
论文作者
论文摘要
我们提出了两种称为催化和抑制作用的补充技术，允许一个人确定给定模式分别是可完整的还是TP不可完整的。从经验上讲，这些技术需要一次在绝大多数情况下一次考虑一次未指定的条目，这使这些技术变得成熟并且是TP完成问题中未来工作的有力框架。有了微小的修改，这些技术也适用于TN完成问题。 我们提供两个主要应用程序。首先，我们通过完整性来表征所有4 x-4模式。总共有78个新的障碍，这是所有$ n $组合的3乘$ n $ case的六倍。其次，我们提供了TN情况下所谓的1变量障碍物的表征，其中包括带有单个未指定输入的模式的表征。这也为证明所有TN完整模式都是可以完整的，这也提供了一个新的部分结果。
We present two complementary techniques called catalysis and inhibition which allow one to determine if a given pattern is TP completable or TP non-completable, respectively. Empirically, these techniques require considering only one unspecified entry at a time in a vast majority of cases, which makes these techniques ripe for automation and a powerful framework for future work in the TP completion problem. With small modifications, these techniques are also applicable to the TN completion problem. We provide two major applications. First, we characterize all 4-by-4 patterns by completability. There are a total of 78 new obstructions of this size, six times as many as the 3-by-$n$ case for all $n$ combined. Second, we provide a characterization of the so-called 1-variable obstructions in the TN case, which includes as a corollary a characterization of patterns with a single unspecified entry. This also provides a novel partial result towards proving the conjecture that all TN-completable patterns are TP-completable.
