问题标签 [np]

Factoring: Gven an integer N, find integers 1 < a, b < N such that N = ab if they exist, otherwise say N is prime.

I know that primality testing is in P, but why not factoring?

Here is my algorithm:

This runs in O(sqrt(N)).

NP 中的任何问题都可以在确定性的指数时间内解决，或者我们可以说 NP 中的任何语言都可以由运行时间为 2^O(n^k) 的算法决定，即 NP ⊆ EXP

通俗地说，我们只是尝试每一种可能的解决方案，然后再决定

但是，有一个简单的例子，我无法弄清楚我提出的想法有什么问题

这里是..

旅行商问题：给定一个无向图 G=(V,E) V=|n|

这是一个众所周知的 NP 完全问题，因此，确实属于 NP

我尝试分析运行时间..像这样：

我只是列出了所有可能的解决方案，并且有 (n-1) 个！总共可能的旅行

然后我检查它们中的每一个，每个可能的旅行都需要 O(n)

总运行时间为 O(n!)

它看起来不能以 2^O(n^k) 为界，即指数时间

这种分析的缺陷在哪里？

或者换句话说，我们如何解释旅行商问题确实可以通过运行时间 2^O(n^k) 的算法来决定

我正在尝试创建一种算法，该算法可以获取一组对象并将它们组织在给定区域中，以便优化包围所有形状的框（通过使用的区域，或通过沿某个维度最大化跨度等） .)。所有的形状都是封闭的和有界的。

这样做的目的是尽量减少使用激光切割机造成的材料浪费。形状是在 CAD 中生成的，可以读入该算法。然后，该算法将获取工作区域（有效激光切割区域）以及任何两个对象之间的最小间距的参数，然后尝试在指定尺寸内组织对象，同时尝试最小化区域使用。或者，该算法还可以尝试最大化沿一个轴的对象位置，同时最小化沿另一维的跨度。这类似于切割要切割的较小工件。

理想情况下，该算法将能够进行平移和旋转，但旋转不是必需的。

例如，此图片描述了所需的转换。

它应该适用于任意但少量 (<25) 的对象。

最后，我不希望任何人为我解决这个问题，但我希望能帮助我找到可以做到这一点的算法，或者开发我自己的算法。谢谢你。

我知道 3-SAT 可以多项式简化为 INDEPENDENT-SET 问题。现在是 INDEPENDENT-SET 问题多项式可简化为 3-SAT 问题吗？那么这些问题是多项式等价的吗？

我认为是这样，因为根据我的观点，INDEPENDENT-SET 问题的每个实例都可以用 3-SAT 表示（在某些情况下，在添加一些额外的边之后）。但是我不清楚我的这种理解。

请帮帮我。

假设你有一组人J，你需要为每个人拍一张照片。他们只有一位摄影师，摄影师有有限的时间T( |T|> |J|) 可用于拍摄每张照片。在任何给定时间，t摄影师T只能拍摄一张照片。中的每个人J只能在 中的某些时间段内拍摄他们的照片T，尽管每个人都被要求至少选择一次他们有空的时间。本质上，根据每个人的可用性，摄影师希望尝试将一个人分配到每个可用的时间段T这样每个人都可以拍照。有没有多项式时间算法来解决这个问题？如果不是，什么非多项式时间问题在多项式时间内简化为这个问题，即如何证明这个问题不在P?

例子：

摄影师有时可用[1, 12, 15, 33, 45, 77]。
人 A 有时有空[12, 33]。
B 人有时有空[1, 12]。
C 人有时有空[1, 12]。

我们可以通过以下选择拍摄每个人：
人 A：33
人 B：1
人 C：12

如果我们从选择 A: 12、 B:开始1，我们将无法找到 的位置C，即我们必须回溯并将 A 重新分配给33。

本质上，我正在寻找一种多项式时间算法来找到适当的时间分配（如果存在），否则能够报告不存在适当的分配。

如何在无向图中找到从源到目的地的顶点不相交路径的最大数量？边缘没有重量。该程序应该能够显示路径的数量并显示每个路径。

我试图了解 NP-Complete 和 NP-Hard 之间的区别。

下面是我的理解

NP-Hard 问题是不能在多项式时间内解决但可以在多项式时间内验证的问题。
NP-Complete 问题是属于 NP 且也是 NP-Hard 的问题。

上面的定义正确吗？如果是这样，那么问题不是在 NP 中而是在 NP-Hard 中。他们不会比 NP-Complete 问题更难，说他们只能在指数时间内解决和验证吗？

据我了解，有两个步骤可以证明问题是 NP 完全的：

1. 给出一个算法，它可以在多项式时间内验证问题的解决方案。也就是说，一种算法，其输入是对问题提出的解决方案，其输出是“是”或“否”，这取决于输入是否是问题的有效解决方案。

2. 证明问题是 NP 难题 - 例如，假设您有一个预言机可以一步计算另一个已知的 NP 完全问题。使用它，编写一个算法，在多项式时间内解决这个问题。

例如，假设我们要证明以下问题是 NP 完全问题：

给定一组整数 ，S是否可以隔离元素的子集S'，使得 中的元素之和S'恰好等于S中未包含的其余元素之和S'？

第一步：验证算法

显然，这在多项式时间内运行：第一个 for 循环运行在O(nm)，第二个运行在O(n).

第 2 步：减少

假设我们有一个预言O(Set S, int I)机可以一步计算子集和问题（也就是说，S 中是否有一个元素的子集总和为 I）？

然后，我们可以编写一个多项式时间算法来计算我们的半子集问题：

如果我在这个过程中犯了任何错误，有人可以告诉我吗？这是我期末考试复习中的一个问题，我不确定我是否完全理解。

我正在写一些问答游戏，如果玩家未能解决问题，我需要计算机来解决问答中的 1 个游戏。

给定数据：

1. 要使用的 6 个数字的列表，例如 4、8、6、2、15、50。
2. 目标值，其中 0 < 值 < 1000，例如 590。
3. 可用的操作是除法、加法、乘法和除法。
4. 可以使用括号。

生成评估等于或尽可能接近目标值的数学表达式。例如，对于上面给出的数字，表达式可以是：(6 + 4) * 50 + 15 * (8 - 2) = 590

我的算法如下：

1. 从上面的（1）生成给定数字的所有子集的所有排列
2. 对于每个排列，生成所有括号和运算符组合
3. 在算法运行时跟踪最接近的值

我想不出对上述蛮力算法的任何智能优化，这将加速它的数量级。另外我必须针对最坏的情况进行优化，因为许多问答游戏将在服务器上同时运行。

今天为解决这个问题而编写的代码是（从项目中提取的相关内容）：

它打印：((((4*6)+50)*8)-2)。用不同的值对其进行了一些测试，它似乎工作正常。我还有一个功能可以删除不必要的括号，但它与问题无关，所以没有发布。

问题在于，由于所有这些排列、组合和评估，这运行非常缓慢。在我的 mac book air 上，它运行了几分钟，例如 1 个。我想让它在几秒钟内运行在同一台机器上，因为许多问答游戏实例将同时在服务器上运行。所以问题是：

1. 我可以以某种方式（按数量级）加速当前算法吗？
2. 我是否缺少针对此问题的其他一些运行速度更快的算法？

是否存在为此的算法，或者有人可以指出我正确的方向吗？

我有一组具有图像的优先用户。每个图像的比例可能为 3:4、4:3 或 1:1。每个用户都有一组不同比例的优先图像。我想制作一个具有零间隙的无限滚动 xy 轴拼贴画。虽然不同形状的 2D 装箱是 NP 难的，但有一些“秘籍”可能会使这更容易：

1. 每个形状应该有 3 种尺寸：大、中和小（例如，3:4 将有 3:4 大、3:4 中和 3:4 小）。
2. 整个拼贴画不需要适合任何形状，因为观众永远不会看到边缘（它是无限滚动）
3. 任何矩形、非正方形形状都可以调整 +/- 10 像素。我们将放大并裁剪另一侧（宽度或长度）以适应新形状。这使得清除高达 20px 的间隙成为可能。
4. 每个形状之间需要有一个 15-25px 的固定边框。此边框大小无法更改。

使用这些参数，我能够直观地构建形状网格。我从这 9 种尺寸开始：http ://cl.ly/image/08373b0r311L和 20px 边框。然后，我使用适合超大矩形的“超级图案”制作了拼贴画（http://cl.ly/image/3h462O3i3k47 ）。请注意，红色形状是由 +/- 10 像素填充的 3:4 形状。在这种情况下，我只需要填充 3:4 的图像。

感谢你们可以提供的任何帮助:)