我所知道的(不是严格意义上的)
我知道关于 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 类?