问题标签 [np]

我在某处读到-如果有人有一天可以证明P = NP，那么我们不能说停止问题可以在多项式时间内解决。你能解释一下为什么吗？

例如，已知集合覆盖决策问题是一个 NP 完全问题。这个问题的输入是一个全域 U、一个 U 的子集族 S 和一个整数 k()。

我感到困惑的一件事是，如果我们让 k=1，那么显然可以通过简单地检查 S 中的每个元素来及时解决问题 |S|。更一般地说，当 k 是常数时，问题可以在 |S| 的多项式时间内求解。这样，只有当 k 也随着 |S| 增加时，时间复杂度才会呈指数级增长，例如 |S|/2、|S|/3...

所以这是我的问题：

1. 我目前的理解是，NP完全问题的时间复杂度测量是根据最坏情况来测量的。谁能告诉我理解是否正确？

2. 我看到有人证明了另一个问题是 NP 难的，他证明输入的集合覆盖决策问题<U,S,|U|/3>可以简化为该问题。我只是想知道为什么他只证明了<U,S,|U|/3>，而不是<U,S,ARBITRARY k>？？这样的证明可靠吗？

非常感谢！

我想知道以下问题是否是 NP-Complete 或者是否有解决它的特定算法：

想象一下，您有一定数量的钱，例如 30 欧元，硬币和特定价值的钞票（0.01 欧元、0.05 欧元、5.00 欧元......）。

我们已经给出了硬币和纸币的数量，您必须将其分配给A、B、C等人。

您希望A有一定数量的钱（例如 10 欧元），B 有不同或相等的数量，等等。

“要求”的钱的总和不大于我们拥有的钱。

所以，问题是：is there a distribution of coins and bills such that every person has the quantity of money that belongs to him?

提前致谢！

我似乎无法区分接受算法和决策算法，尽管我觉得我确实理解了这个概念。我目前正在阅读“算法简介”（Cormen），并且在 NP-Completeness 章节之后遇到问题，因为它指出

“对于其他问题，例如图灵的停机问题，存在接受算法，但不存在决策算法”。

到目前为止，这对我来说确实有意义，但我们更进一步说

我们要证明 P 也是

“因为语言的类别是由多项式时间算法决定的，我们只需要证明，如果 L 被多项式时间算法接受，它就是由多项式时间算法决定的。”。

然后我们继续构建一个接受算法的模拟，它额外检查接受算法的行为，如果前一个算法接受输入，则输出 1，否则输出 0。

但是，如果我们可以构造这样的算法，Halting Problem 怎么可能有一个接受但没有一个决策算法呢？

对于计算机视觉中的一些项目，我在高维空间中有N个点。我想选择其中k个彼此“最有区别”的。例如，它可以转换为所选点之间的距离总和最大。或者可能是多面体的体积最大。但一般来说，任何有直觉的东西都可以去。

不出所料，我想找到这些代表点。

有两个问题：

• 更常用的“最可区分”点的定义是什么？他们是否更改了用于查找这些点的算法？
• 找到点的算法是什么？它高度提醒我最大加权集团问题。是NP难问题吗？在这种情况下，我们可以对最优解做出一些好的近似吗？

在维基百科中，我找到了这张图。我不明白在假设 p=np 下我们如何得到 p=np=np-complete？

我必须找到从 D 点到 R 点的最短路径。这些是固定点。这是一个例子：

盒子还包含墙壁，除非你打破它们，否则你无法穿过它们。每破墙都会花费你，比如说“a”点，其中“a”是一个正整数。每一个不涉及墙的动作都会花费你1分。

任务是找出所有成本最低的路径，即破墙数量最少的路径。

由于框的宽度可以达到 100 个单元格，因此使用回溯是无关紧要的。它太慢了。我想出的唯一解决方案是这个：

1. 如果没有墙壁，向东或向南
2. 如果南有墙，检查西是否有墙。西有墙，破南墙。如果西边没有墙，就往西走，直到你找到一个没有墙的南边牢房。对南部和东部重复此过程，直到您按此顺序超过破墙的成本。如果从西边的路径进入同一个地方，就好像我打破了南墙并且花费相同或小于“a”点，那么使用这条路径，否则刹车南墙。
3. 如果上面没有遇到，根据盒子边界来制动南墙或东墙。

重复步骤 1、2、3，直到“乘客”到达 R 点。这 3 个步骤之间存在“else-if”关系。

你能想出一个更好的问题算法吗？我用 C++ 编程。

有时评估积分非常困难，但很容易验证解是否正确。在我看来，它至少应该是 np，但我对这个概念的理解是有限的，我可能会遗漏一些东西

编辑：为了清楚起见，我很好奇算法的复杂性，该算法找到函数的反导数以求解不定积分，而不是计算定积分的数值近似。

我不是在寻找答案，因为这是他们编码问题的实习面试问题。相反，我正在寻找朝着正确方向前进的线索。

基本上，用户输入 2 个参数。商品数量和价格点。例如，如果用户输入 3 件商品和 150 美元的价格点，算法应该找到尽可能多的接近价格点 150 的组合。

我已经认真考虑过这个问题，我最初的尝试是将价格点除以商品总数。但是这个答案只给了我每个项目的限制范围。

这个问题是 P NP 类型的问题吗？

The Subgraph Isomorphism (SI) problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H.

This is a NP-Complete problem .

I want to know its relation with the SAT problem.
In particular, I want instances of this problem can be solved throughout SAT Solver(like miniSAT).I need an alorithm which can do a mapping from SI to SAT problem in polynomial time and then SAT assignment can be used to find a mapping from nodes of G to nodes of H .

Any idea ???