Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

关于 X3C-Y 实例和 X3C 实例对应关系的疑问 #9

Closed
SadPencil opened this issue Jan 6, 2021 · 2 comments
Closed

关于 X3C-Y 实例和 X3C 实例对应关系的疑问 #9

SadPencil opened this issue Jan 6, 2021 · 2 comments
Labels
X3C-Y X3C-Y

Comments

@SadPencil
Copy link

SadPencil commented Jan 6, 2021

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$也一样,怎么知道这个对应关系?

@sailist
Copy link
Owner

sailist commented Jan 7, 2021

证明 NPC 时,我们是根据 X3C 实例构建出的 X3C-Y 的实例,因此所有的下标是显式出现的,所以这个对应关系在构建的过程中就存在,而不是构建完后 X3C-Y 实例就是完全崭新的 D={d1,d2,...,dn} 了

@sailist sailist changed the title 关于 X3C-Y 的疑问 关于 X3C-Y 实例和 X3C 实例对应关系的疑问 Jan 7, 2021
@sailist sailist added the X3C-Y X3C-Y label Jan 7, 2021
@SadPencil
Copy link
Author

懂了👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
X3C-Y X3C-Y
Projects
None yet
Development

No branches or pull requests

2 participants