我在搜索NP和NP-complete问题的区别。我在StackOverflow上找到了Jason的一个很好的答案。关于NP-complete问题,他说:
一个NP问题X,它可以在多项式时间内将其他任何NP问题Y减少为X。 直观地说,这意味着如果我们知道如何快速解决X问题,我们就可以快速解决Y问题。 精确地说,如果存在一个多项式时间算法f将X问题的实例x转换为Y问题的实例y = f(x),并且具有以下特性:当且仅当x的答案是yes时,f(x)的答案也是yes。
我的问题是:哪个是NP-complete问题,X还是Y?
一个NP问题X,它可以在多项式时间内将其他任何NP问题Y减少为X。 直观地说,这意味着如果我们知道如何快速解决X问题,我们就可以快速解决Y问题。 精确地说,如果存在一个多项式时间算法f将X问题的实例x转换为Y问题的实例y = f(x),并且具有以下特性:当且仅当x的答案是yes时,f(x)的答案也是yes。
我的问题是:哪个是NP-complete问题,X还是Y?