0

我所知道的(不是严格意义上的)

我知道关于 P 和 NP 类的相等性有一个悬而未决的问题,只要没有已知的算法可以在 P 时间内解决 NP 问题,那么我们就可以区分此类问题的时空可解性。

另外,我知道您可以在问题之间进行(多项式时间)减少,因此如果您知道一个问题属于某个类,那么另一个问题也将属于该类。

另外,我知道Simplex算法可以解决线性规划的问题

我想知道的

我想知道如何“猜测”问题是否属于 NP 类。它是否与问题的约束、约束的数量、约束的“类型”有关?

一个例子

在此链接https://www.geeksforgeeks.org/maximum-profit-by-buying-and-sales-a-share-at-most-k-times/我们可以看到解决“通过购买和获得最大利润”的算法使用动态编程最多卖出 k 次”。

但是,如果我们增加约束会怎样。假设我们受限于净资产(我们没有无限的钱),或者我们一次可以买卖多只股票,但我们受限于在给定时间内可以买卖的股票数量,或者我们可以选择多种公司的多种股票,但我们可以拥有的股票总数有限。

我们怎么知道什么样的约束使问题越来越难从 P 到 NP Class ?一个问题应该有什么样的约束才能确定这个问题属于 P 类还是 NP 类?

4

1 回答 1

1

您可以通过将已知为 NP-Hard 的问题简化为手头的问题来证明问题的 NP-Hardness。更正确的是,您应该首先制定手头优化的决策问题版本。然后,将 NP-Complete 问题简化为决策版本。通过找到有效的约简,您可以证明您的优化问题是 NP-Hard。查看减少的想法:https://www.wikiwand.com/en/Reduction_(complexity)

于 2020-01-08T21:10:46.257 回答