问题标签 [p-np]

例如，关于这个多项式时间的整个事情让我感到困惑：我想用多项式时间算法编写一个程序，它只会从一组中选择 4 个总和为 0 的整数。例如：假设我有以下一组整数 {8, 20, 3, -2, 3, 7, 16, -9}。如何在多项式时间内从一组中仅选择 4 个总和为 0 的不同整数，而无需检查除 4 之外的所有可能长度？请注意，在程序中，我不需要搜索任何其他可能的长度而不是 4。我的预期解决方案是 {8, 3, -2, -9} = 0。完全清楚我只需要集合中的 4 个整数 { 8、20、3、-2、3、7、16、-9}。

编辑：我是否会找到 {8, 3, -2, -9} 的多项式时间解，即使我仅将原始集合的长度从 8 个整数增加到 100 个整数，而我仍然必须选择总和为的 4 个元素0 但从 100 个整数的集合中，它仍然是关于输入大小的多项式快速（即用于存储输入的位数）？

有哪些 NP 问题可以简化为 NP 完全问题但不能反过来的例子？当我读到 NP 和 NP-complete 时，我认为映射将是一对一的，因此对它们进行分类是愚蠢的。但是，肯定存在只能在一个方向上还原的问题。我有兴趣了解他们。

在下页P=NP问题的官方链接中：

P=NP 问题官方说明

, 提到了一个为 400 名大学生组织住宿的问题, 宿舍最多可容纳 100 人, 并且院长给出了一个“不相容”的学生对的列表, 即他们可以不能住在一起。该问题进一步表明，从头开始构建这样的列表将是困难的/困难的。但是，我做了一些思考并提出了以下解决方案：

我们通过计算可能的对的确切数量来继续，这可以如下完成：

首先，我们从 400 个可用学生中选择 100 个学生。=( ⁴⁰⁰ C ₁₀₀ ) 方式。^{接下来，我们以100} C ₂的方式

从 100 个学生的集合中选择 2 个学生。然后对于每个集合，如果该对不存在于院长的一对不兼容集中，则将其“添加”到最终结果集中。 我知道这个制作清单的过程需要很长时间，因为清单本身很长。但是，如果我们考虑第一组 400 名学生中的 100 名学生的组合，以便为少数幸运学生提供运气（我的意思是，如果这是一种幸运抽奖，最终只选择了第一组 100 名学生），那么这将是一个简单的问题！

无论如何，我们可以在这个问题中“判断”解决方案集是否存在，因为我们可以通过查看院长的不相容学生列表来直接说明是否有任何对，因为所有这些，只有所有那些不应该在结果集中所以如果有 50 个这样的配对，这意味着有 100 个不相容的学生，我们可以从这个列表中选择第一个 50 个，然后从剩下的 350 个学生中选择其他 50 个？这似乎不像 3SAT 问题那样“难”，只要告诉解决方案就足够了。（在这种情况下，组合总数为⁴⁰⁰ C ₁₀₀ * [ ¹⁰⁰ C ₂ - 所选列表和院长列表中的对数]

（这也可以写成⁴⁰⁰ C ₁₀₀ * [ 院长列表中的¹⁰⁰ C ₂ MINUS 对]，其中 MINUS 是数据库术语中的操作。

请阐明我的研究，我是对还是错？

谢谢

我从事SharePoint 编程。我最近熟悉了一个名为 Sharepoin Pnp 的主题。sharepoint pnp 的本质是什么？什么时候应该使用它？Web 部件和其他 SharePoint 编程部件（如CSOM与 sharepoint pnp ）有什么联系？谢谢亲爱的朋友们的建议。

根据库克定理，

任何 NP 问题都可以在多项式时间内转换为 SAT

我知道SAT是一个NP完全问题。因此，是否准确地说：如果我们可以将搜索问题 A（在 NP 中）以多项式步数简化为问题 B，那么问题 B 一定是 NP 完全的？

实际上，我在没有使用 Pnp Js Rest Api 的情况下与 SharePoint 一起工作。我在 SharePoint 本身上托管捆绑的文件。当我进行构建时 --watch 观察它的变化，但在构建后没有反映在 html 文件中。

我是 Sharepoint 的新手，我遇到了一个问题。我正在使用 PnP/PnPjs，并且正在尝试从站点列之一中获取选择字段。我曾尝试使用 SPWeb 等，但在打字稿中存在问题。有没有办法可以导入这个或其他方式我可以获取这些数据？

我如何获得子术语的扁平化版本，或者只是最后一级/层的术语。例如：TermSet --> Term --> ChildTerm 如何在 SPFX webpart 中获取子术语？我可以抓住条款集下的条款，但我不能再深入了。

我所知道的（不是严格意义上的）

我知道关于 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 类？

该算法需要从给定列表中生成所有可能的组合（不包括空集）。

该算法将花费 O(2 ⁿ ) 时间复杂度来生成所有组合。但是，我不确定改进的算法是否可以降低时间复杂度。如果存在改进的算法，请分享您的知识！

如果它需要 O(2 ⁿ ) 是指数的，我想了解一下这个算法属于 P、NP、NP-Complete 或 NP-Hard 的哪个类。提前致谢 ：）