VLSI芯片测试问题：坏芯片超半数时无法判定好芯片的原因解析

问题背景回顾 #

现有n个外观一致的VLSI芯片，两两测试的规则如下：

• 好芯片的测试结果始终准确；坏芯片的结果不可信，且可串通欺骗。
• 两两测试的推断逻辑：
  • 互相报告对方是好芯片 → 两者均好或均坏
  • 其余所有情况 → 至少一个是坏芯片

我们需要证明：当坏芯片数量k > n/2时，无论采用何种两两测试策略，都无法确定哪些是好芯片。

核心证明思路：构造不可区分的对称场景 #

我们通过构造两种测试结果完全一致的场景，说明测试者无法判断哪一种是真实情况，因此无法确定好芯片。

步骤1：定义两个对称场景 #

假设真实场景为场景S1：存在k个坏芯片（k > n/2），剩余n-k个为好芯片。
我们构造一个镜像场景场景S2：将S1中的好芯片全部标记为坏芯片，坏芯片全部标记为好芯片。此时S2中“好芯片”数量为k，“坏芯片”数量为n-k（显然k > n-k，因为k > n/2）。

步骤2：坏芯片的串通欺骗策略 #

在场景S1中，坏芯片可以按照以下规则串通，完全模仿场景S2中“好芯片”的测试行为：

• 当坏芯片测试另一个坏芯片时，互相报告对方是好芯片（对应S2中两个好芯片互相测试的准确结果）；
• 当坏芯片测试好芯片时，报告该好芯片是坏芯片（对应S2中好芯片测试坏芯片的准确结果）；
• 当坏芯片被好芯片测试时，好芯片会如实报告它是坏芯片——这恰好和S2中“坏芯片被好芯片测试”的结果一致（S2中该坏芯片是原好芯片，被原坏芯片（现在是好芯片）测试时，会被如实报告为坏）。

步骤3：两种场景的测试结果完全一致 #

对比S1和S2的所有两两测试结果：

• 原坏芯片之间的测试：S1中坏芯片互相报告好，S2中这两个是好芯片互相报告好 → 结果一致；
• 原坏芯片与原好芯片的测试：S1中原坏芯片报告原好芯片为坏，原好芯片报告原坏芯片为坏；S2中原坏芯片（好芯片）报告原好芯片（坏芯片）为坏，原好芯片（坏芯片）报告原坏芯片（好芯片）为坏 → 结果一致；
• 原好芯片之间的测试：S1中好芯片互相报告好；S2中这两个是坏芯片，它们串通互相报告好 → 结果一致。

步骤4：为什么坏芯片超半数是关键条件？ #

只有当k > n/2时，场景S2中的“好芯片”数量k才会超过半数，我们才能构造出这种完全对称的测试结果：

• 如果k ≤ n/2，那么S2中的“好芯片”数量k ≤ n-k（原好芯片数量），此时原好芯片之间的测试结果（真实场景中互相报告好）无法被镜像场景中的坏芯片完全模仿——因为镜像场景中坏芯片数量更多，它们的串通行为无法覆盖所有两两测试的真实模式，测试者会发现结果存在矛盾，从而可以区分真实场景和镜像场景。

结论 #

当坏芯片数量超过n/2时，坏芯片可以通过串通构造出与“原坏芯片是好芯片、原好芯片是坏芯片”完全一致的测试结果，导致测试者无法判断哪种情况为真，因此无法确定哪些芯片是好芯片。

内容的提问来源于stack exchange，提问作者XuanZ