complexity-theory - 如果 A 是 NP 完全的并且如果从 A 减少到 B，是否意味着 B 也是 NP 完全的？

Question

假设 A、B 和 C 是决策问题。还假设 A 是多项式时间可约化为 B 且 B 是多项式时间可约化为 C。如果 A 和 C 都是 NP-完全的，那么这是否意味着 B 也是 NP-完全的？

我知道，如果 A 是 NP 完全的并且它是多项式时间可简化为 B，那么 B 是 NP 难的。但是，为了使问题成为 NP 完全问题，它必须满足 (1) 它在 NP 中，并且 (2) 它是 NP-hard。

我不知道如何证明 NP-complete 的第一个要求。

Answer 1

如果 A 是 NP 完全的并且多项式时间可简化为 B，则 B 是 NP 难的。

如果 B 是多项式时间可简化为 C 并且 C 是 NP 完全的，则 B 在 NP 中。

NP-hard 中的 NP 问题是 NP-完全的。

证明 B 是 NP 完全的另一种方法是注意任何两个 NP 完全问题（例如 A 和 C）彼此是多项式可约化的，因此 B 等价于（双向多项式可约化）任何 NP 完全问题.

Answer 2

Les try Out:- (REC= Recursive lang, REL=Recursive Enumerable lang, UD= Undecidable, D= Decidable)  

if P < Q than

  UD-->UD

  D<--D

  P<--P

  P,NP<--NP

  NPC-->NPH

  P,NP--> we can't anything it may be (NP,NPH,REC,REL)

  REC<-- REC

  REL<--REL

  D--> Can't say anything.

   ?<--UD


we know that P is Proper Subset of NP. (as P != Np)

and All NPC is NPH.

to prove NPC:-
""
if NP reducible to X problem than that X is NPH.

if X reducible to any NPC than that X is NPC.""

p^NPC=0