将A还原为B:对还是错 [英] Reduction of A to B : True or False

问题描述

有两个语句:如果决策问题A可简化为决策问题B的多项式时间(即A≤pB )，并且B是NP完全的，则A必须是NP完全的.

并且:

如果决策问题B是多项式时间可归结为决策问题A的多项式(即B≤pA )，并且B是NP完全的，那么A必须是NP完整的.

以上哪种说法是正确的?

您还可以给出解释吗?

解决方案

第一个语句为假，因为这意味着通过求解B然后应用多项式时间算法可以求解A，但也许还有另一种方法可以解决A不需要求解B，也许只是多项式.

第二句话是正确的，因为这意味着您可以通过先求解A来求解B，然后应用多项式时间算法来求解B，但是B是NP完全的，所以A必须是NP完整的

There are two statements: If a decision problem A is polynomial-time reducible to a decision problem B (i.e., A≤ pB ), and B is NP-complete, then A must be NP-complete.

And:

If a decision problem B is polynomial-time reducible to a decision problem A (i.e., B≤ pA ), and B is NP-complete, then A must be NP-complete.

Which of the above statements are true?

Can you also give explanation?

解决方案

the first statement is false because it means that by solving B and then applying some polynomial time algorithm you can solve A but maybe there is another way to solve A that doesn't require solving B and maybe it's only polynomial.

the second statement is true because it means that you can solve B by first solving A then apply some polynomial time algorithm to solve B but B is NP-complete so A has to be NP-complete

这篇关于将A还原为B:对还是错的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！