关于货郎延伸问题NPH证明是否可以将货郎延伸问题等价转换成货郎优化问题来证明？
就是将已知一部分货郎旅游路径上的点和与这些点相连的边都去掉，形成一个新的图G'，将已知一部分货郎旅游路径上最后一个点v作为起点，将B减去已知一部分货郎旅游路径上边长之和得到的C作为新的总行程不小于C的实数，这样就形成了一个新的TSP（优化）问题。而TSP是NPH，那么货郎延伸问题也是NPH。可以这样证明吗？

这是否是:

但是应该也不影响后文推导思路。
此外，

这样是否好一点：

• 第一个红框部分是不是应该是 C^{\prime} \subseteq C 的关系
• 第二个红框部分加上 i \neq j 是不是更好

在 x3c.md 文件中存在下面一句话：

3DM 实例 M 中存在完美对集，当且仅当 X3C 实例 C 中存在 S 的严格覆盖。问题得证。

这句话的当且仅当为什么成立？是不是应该改为左边推出右边？

例如，如果当且仅当成立，则右边推出左边成立。
右边，对于X3C的一个实例

S={1,2,3,4,5,6} 
C={{1,2,3},{1,2,4},{1,2,5},{1,2,6},{4,5,6}}

而言，如何推出左边成立？

这里构造的实例仅是ci与cj的交集数量=0的情况，题干所给的是ci与cj的交集数量≤1，找到的这种构造方式没有问题。但若题干替换为ci与cj的交集数量=1，该如何构造对应的T和D？

这个说“每个三角形对应的边集中的三条边至少有一条边也被覆盖，因此在三角形集中必须选择边集中还未覆盖的边相连的点，最后将每个三角形集选满两个点”是否更好一点？（因为每个三角形对应的边集可能没有两个未覆盖的边，但是每个三角形要选满两个点。）

在https://sailist.github.io/AdAlgo/turing/3.html中，“此时，根据图灵归约的定义，货郎优化问题是 NP-hard，因此货郎判定问题也是 NP-hard。”这句话是否是说反了呢？

（红线部分）
存在？
bi,1 , ... ... ,bi,6?
dj,1 , ... ... ,dj,5?
dj,1 , ... ... ,dj,3?
还有一个问题就是，x3c-y是x3c的子问题，那必要性那部分可以不证明吗？

2.md 文件中：

(<-) 当 GPAR 存在划分时候， 因为 $$S(A)+2S(A)+B=3S(A)+B>2S(A)$$

所以GPAR 问题中新增的两个元素 ${S(A),2S(A)+B}$ 不可能同时在一个划分子集中。

此时将从原 $A$ 中挑选出的元素作为 $A'$，则下式成立（GPAR的划分条件）：

$$2S(A)+B+S(A')=2(S(A)+S(A-A'))$$

注：规定一下符号，B'和B-B'是GPAR问题里划分出来的两个子集，A'和A-A'是PAR问题里划分出来的两个子集

我觉得这段话想要表达的意思是，如果GPAR存在划分，这个划分必定是B'=A'∪{2S(A)+B}，其他的划分不可能存在，然后再用2S(A)+B+S(A')=2(S(A)+S(A-A')) 这个式子解出等式。

然而，这里只说明了两个元素 ${S(A),2S(A)+B}$ 不可能同时在一个划分子集中。

应当说明以下情况：

• S(A)和2S(A)+B 不能都在B' 中，也不能都在B-B' 中（即原答案所述）
• S(A) 在 B' 中，同时 2S(A)+B 在 B-B' 的这种情况不存在（否则推出矛盾）

因此，只有以下情况是可能的：

• 2S(A)+B在B'中，S(A)在B-B'中

令PAR问题的A'为A∩B'，A-A'自然为A∩(B-B')

套用 2S(A)+B+S(A')=2(S(A)+S(A-A')) 这个式子解出等式，完成后面的证明。

直接套用的话感觉说的不严密。

【注：经过底下的评论的纠正，进行了修改。如果感觉后面的对话有突兀的感觉，请翻看编辑的历史记录。】

在 3.md 文件中：

若 X3C-Y 中存在 $D'$ 是 T 的严格覆盖，对于同一个 j 对应的五个元素 $d_{j,1}\sim d_{j,5}$，可得要么同时选中 $d_{j,1}\sim d_{j,3}$，要么同时选中 $d_{j,4},d_{j,5}$ 两个。

此时令严格匹配 D' 中的每三个元素 $d_{j,1}\sim d_{j,3}$ 对应选择原 X3C 问题中的 $c_j$，可得该种方式构成的子集 $C'$，恰好为对 $S$ 的严格覆盖。

上述说明比较难以理解，下面通过一个简单的例子来说明对应过程：
例如，
X3C 实例项集合为 C = {c1-c5}，5个元素，那么相应构建的 X3C-Y 实例的项集合即为 D={d1(1-5),d2(1-5),...,d5(1-5)}，共 25 个元素

假如可以找到一个 X3C 的严格覆盖  C'={c1,c3,c5}，那么X3C-Y 的严格覆盖 D' 就是 {d1(1-3),d3(1-3),d5(1-3), d2(4-5),d4(4-5)}，反之同理。

这里，首先，我感觉 反之同理 不是那么明显，在证明X3C->X3C-Y的时候我们可以知道，哪个是d_{i,1}，哪个是d_{i,4}，因为d是通过c构造的。但是反过来，这里证明X3C-Y->X3C时，对于D或者D'中的任意一个元素d，怎么知道它原本对应的是d_{i,j}中的哪个i和j？

再往上的令严格匹配 D' 中的每三个元素 $d_{j,1}\sim d_{j,3}$ 对应选择原 X3C 问题中的 $c_j$也一样，怎么知道这个对应关系？