问题标签 [np]

斯坦福大学的 Tim Roughgarden 教授在教授MOOC时说，NP 类问题的解决方案必须是多项式长度。但是维基百科的文章说 NP 问题是决策问题。那么什么类型的问题基本上属于 NP 类？并且没有必要说此类问题的解决方案具有多项式长度输出（因为决策问题必须输出 0 或 1）？

计算机科学中是否有任何重大问题只能在双指数时间内解决？如果它们存在，那么它们属于哪一类问题？

给定一组 n 种类型的矩形 3-D 框，其中第 i^th 框的高度为 h(i)，宽度为 w(i)，深度为 d(i)（均为实数）。您想创建一个尽可能高的盒子堆叠，但如果下层盒子的 2-D 底座的尺寸都严格大于 2-D 盒子的尺寸，您只能将一个盒子堆叠在另一个盒子的顶部。上盒的 D 底座。当然，你可以旋转一个盒子，让任何一面作为它的基础。不允许在一个盒子上使用多个实例。

这个问题已在 SO（Box stacking problem）上提出，但没有“没有重复”的限制。我们如何使用 LIS 解决这个问题。

我设计了以下解决方案，可以辩论吗

其中 h[j'] 只不过是如果第 j 个框已经用于计算 H[i] 。由于允许旋转，H[j] 可以是第 j 个框的宽度或深度

考虑这里描述的问题（转载如下。）可以将一些更知名的 NP 完全问题简化为它吗？

问题：

有一排房子。每个房子都可以涂上三种颜色：红色、蓝色和绿色。用某种颜色粉刷每个房子的成本是不同的。你必须给所有的房子涂漆，这样相邻的两个房子就没有相同的颜色。你必须以最低的成本粉刷房屋。你会怎么做？

注：将房屋 1 涂成红色的成本与将房屋 2 涂成红色的成本不同。房屋和颜色的每种组合都有其自身的成本。

我知道图形着色是一个 NP 完全问题。我想知道是否添加对可以具有给定颜色的顶点数量的限制会使问题更简单？我似乎找不到任何算法可以做到这一点。例如，如果我有一个图形，我想说“这个图形的最小着色是什么，使得每种颜色最多有 3 个顶点”，或者如果它简化了问题“有没有办法用这个图形着色4种颜色，每种颜色最多有3个顶点”？

谢谢！

我想知道编码一个布尔公式需要多少位

@ 是 SAT 的一个实例。我认为它是 4 位，因为可能组合的总数是 2（power4）。那是对的吗？我应该计算 OR、NOT 和 AND 来计算编码所需的位数吗？我搜索了很多，但在这方面找不到任何东西。

Suppose you have a graph G = (V, E) that represents the floor plan of a one-story shopping mall. The individual stores are represented by vertices, and the edges between vertices represent some arbitrary definition of stores being close to each other.

Recently, there has been an increase in the amount of shoplifting that occurs in this mall, so management decides to make it so that every store either:

• Has a security guard stationed in it

• Or is close to a store that has a security guard stationed in it

While hiring as few security guards as possible.

How would you prove this optimization problem is NP-complete? I feel like it's a simple reduction from the independent set problem, but I want to make sure.

在背包问题中，唯一的约束是拣选物品的总大小不大于包裹的总大小。我们知道背包问题是 NP 完全问题。

但是，如果我们有另一个选择固定数量项目的约束，那么这个问题仍然是 NP-Complete 吗？问题的正式描述如下所示，

最大化 $\sum_{j=1}^n p_j x_j$

st $\sum_{j=1}^n w_j x_j < W$

这是我研究中的一个公式化问题，我不确定它是否是 NP-Complete 的。请帮我。谢谢！

是否有确定性算法来检查图是否包含从源到目的地的顶点不相交路径，具有复杂性O(nm^2)（n 是顶点数，m 是边数）还是这个 NP-Hard（如果是，为什么）？顶点不相交路径是指没有公共内部顶点的路径。例如。

顶点不相交但

不是因为 a 是公共顶点。

完整的问题是：

对于连通无向图，G = (V, E)

和所需的顶点集D，D is a subset of V（即D \in V）

是否NP-hard要找到一个minimum dominating set包含所需顶点集的D?