Skip to content

10 P/NP Problems

常见问题的 P/NP 属性

\(\text{SAT}\) \(\text{Hamilton cycle}\) \(\text{Vertex cover}\)
类别 \(\text{NP-complete}\) \(\text{NP-complete}\) \(\text{NP-complete}\)

Knapsack Problems 一般是 NPH，但是还要看 \(p_max\)，如果 \(p_max\) 是多项式，那么就不是 NPH 了；也有说是NPC？我不知道。。

Shortest-Path 的判定版本是P类问题（可通过 Dijkstra/BFS 在多项式时间内解决）。

P, NP, NPH and NPC

定义

  • P：可在确定性多项式时间内解决的问题
  • NP：可在非确定性多项式时间内验证解的问题
  • co-NP：补问题属于 NP
  • NPH：所有 NP 问题都能多项式归约到该问题
  • NPC：NP 和 NPH 的交集

If X is a problem in class NP, then how many of the following statements is/are TRUE?

  • There is no polynomial time algorithm for X.
  • There is a polynomial time algorithm for X.
  • If X can be solved deterministically in polynomial time, then P = NP.
答案

0

基本概念

Which of the following is TRUE about NP-Complete and NP-Hard problems?

\(\textnormal{A}\). If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X in polynomial time.

\(\textnormal{B}\). The first problem that was proved to be NP-complete was the circuit satisfiability problem.

\(\textnormal{C}\). NP-complete is a subset of NP-Hard

\(\textnormal{D}\). All of the other three.

答案

\(\textnormal{D}\)

NP-complete problems are the hardest problems in NP-hard problems in terms of computational complexity.

答案

\(\textnormal{F}\)

图灵机的种类

  • 确定型 (deterministic) 图灵机：它能够在每个阶段执行一条指令，随后根据当前指令的内容来选择下一条要进行的唯一的指令。
  • 非确定型 (nondeterministic) 图灵机：它根据一个有限集合来自由选择下一步要执行的指令。并且若执行时存在能够找到解的步骤，那么它一定能够选择得到此解的正确指令。
    • 它可以对所有的可判定问题给出决策，但无法解决不可判定问题。

How many of the following arguments are correct?

  • For non-deterministic Turing machine, “non-deterministic” means that the operations of the machine are random, such that the results of the operations are not deterministic.
  • If a decision problem A can be reduced to B, then it means that problem A is strictly easier than B in terms of computational complexity.
  • A decision problem in P is also in both NP and co-NP.
答案

非确定性图灵机的非确定性不等于随机性，陈述 1 错误。

若判定问题 \(A\) 可归约到问题 \(B\)，其含义是若能解决问题 \(B\)，则可以解决问题 \(A\)，这只能推导出 \(A\) 的计算复杂度 小于或等于 \(B\)，而非 严格低于 \(B\)。例如，所有 NP 完全问题之间都可以互相多项式归约，它们的计算复杂度是等价的，而非严格的难易之分，故陈述 2 错误。

\(P\) 类中的任意判定问题，同时属于 \(NP\) 和 \(co\text{-}NP\)，陈述 3 正确。

综上所述，答案为 \(1\)。

停机问题

The decision problem HALTING returns TRUE, if, for a given input \(I\) and a given (deterministic) algorithm \(A\), \(A\) terminates, otherwise it loops forever. The HALTING problem is NP-complete.

答案

停机问题是不可判定问题，而 P/NP 问题都是可判定问题，故答案为 \(\textnormal{F}\)

P/NP 问题的判定

A boolean formula is in disjunctive normal form (DNF) if it is a disjunction (OR) of one or more conjunctions (AND) of one or more literals. A literal is a variable or its negation. For example, the formula \((x ∧ ¬y ∧ z) ∨ (¬x ∧ z) ∨ (w ∧ y ∧ ¬z)\) is a DNF formula. In DNF-Sat you are given a DNF formula, and the goal is to tell whether that formula is satisfiable. We claim that the problem DNF-Sat is in \(\text{P}\).

答案

设 DNF 公式的总文字数为 \(n\)，则遍历所有子句的时间是 \(O(n)\)，每个子句检查矛盾文字的时间是子句内文字数，总时间仍为 \(O(n)\)，该算法是多项式时间（\(O(n)\)）的，故 DNF-Sat 属于 \(\text{P}\) 类问题，答案为 \(\textnormal{T}\)

Consider a Knapsack problem with \(n\) items. If no items have a size larger than \(n^3\), then it is no longer NP-hard.

答案

0-1 背包问题的动态规划法的时间复杂度为 \(O(n \times capcity)\)，若每个物品的尺寸 \(s_i \leq n^3\)，则所有物品的总尺寸 \(\leq n \times n^3 = n^4\)，时间复杂度 \(= O(n \times n^4) = O(n^5)\)，多项式时间可解，不属于 NP-hard，答案为 \(\textnormal{T}\)

If P = NP then the Shortest-Path (finding the shortest path between a pair of given vertices in a given graph) problem is NP-complete.

答案

\(\textnormal{T}\)

The following problem is in co-NP.

Given a positive integer \(k\), is \(k\) a prime number?

答案

\(\textnormal{T}\)

If P = NP then NP = co-NP.

答案

\(\textnormal{T}\)

归约

Any problem in P is polynomial-time reducible to any other problem in P.

答案

\(\textnormal{T}\)

If \(L_1 \leq_p L_2\) and \(L_2 \in NP\), then \(L_1 \in NP\).

答案

\(\textnormal{T}\)

If \(L_1 \leq_p L_2\) and \(L_1 \notin NP\), then \(L_2 \notin NP\).

答案

\(\textnormal{T}\)

题目 2

All the languages can be decided by a non-deterministic machine.

答案

不可判定的语言（例如停机问题对应的语言）既不能被 DTM 判定，也不能被 NDTM 判定，故答案为 \(\textnormal{F}\)

题目 3

All NP problems can be solved in polynomial time in a non-deterministic machine.

答案

\(\textnormal{T}\)

All NP problems are decidable.

答案

\(\textnormal{T}\)

题目 4

A language L belongs to NP if there exist a two-input polynomial-time algorithm A that verifies language L in polynomial time.

答案

\(\textnormal{T}\)

题目 5

To prove problem B is NP-complete, we can use a NP-complete problem A and use a polynomial-time reduction algorithm to transform an instance of problem B to an instance of problem A.

答案

为了证明问题 B 是 NP 完全的，需要使用一个已知的 NP 完全问题 A，并通过多项式时间归约算法将 A 的实例转换为B的实例（即从 A 归约到 B），而不是从 B 归约到 A，这样才能证明 B 是 NP 难的，从而结合 B 在 NP 中得出 B 是 NP 完全的。故答案为 \(\textnormal{F}\)

CP to VCP

About Vertex Cover problem, which of the following statements is FALSE?

\(\textnormal{A}\). It is an NP problem.

\(\textnormal{B}\). The time complexity of its verification algorithm is \(O(N^3)\), where \(N\) refers to the number of nodes.

\(\textnormal{C}\). It is polynomial-time reducible to Clique problem, but not vice versa.

\(\textnormal{D}\). It is an NP-complete problem.

答案

\(\textnormal{C}\)

NPC 判定

A Hamiltonian Cycle (or Circuit) in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex. Finding a Hamiltonian Cycle is a well-known NP-complete problem. Let's consider the following two new variants of the Hamiltonian problems:

P1) Long Cycle problem: A Long Cycle in a graph G is a cycle that goes through at least half of the vertices of G.

P2) Hamiltonian Path problem: A graph G has a Hamiltonian path from s to t if there is an s to t path that visits all of the vertices of G exactly once.

Which of the following statement is correct:

\(\textnormal{A}\). Only the Long Cycle problem is NP-Complete.

\(\textnormal{B}\). Only the Hamiltonian Path problem is NP-complete.

\(\textnormal{C}\). Both the Long Cycle problem and the Hamiltonian Path problem are NP-complete.

\(\textnormal{D}\). None of the Long Cycle problem and the Hamiltonian Path problem are NP-complete.

答案

\(\textnormal{C}\)

图论

Consider a bipartite graph \(G(A,B,E)\). (Recall that a graph \(G\) is bipartite if the vertex set of \(G\) can be partitioned into \(A\) and \(B\) such that all the edges of \(G\) has one endpoint in \(A\) and the other in \(B\).) A matching on \(G\) is a subset \(M\) of \(E\), such that no two edges in \(M\) have a common vertex. A vertex cover is a subset \(C\) of \(V\), where every edge in \(E\) must have at least one endpoint in \(C\). Denote by \(| S |\) the cardinality of a set \(S\). Which of the following statements is false?

\(\textnormal{A}\). For a minimum vertex cover \(C\), \(| C | = \min\{ | A |, | B | \}\)

\(\textnormal{B}\). For any vertex cover \(C\) and any matching \(M\), \(| C | \geq | M |\)

\(\textnormal{C}\). For a minimum vertex cover \(C\) and a maximum matching \(M\), \(| C | = | M |\)

\(\textnormal{D}\). Exactly one of the other options is wrong

答案

在二分图中，最小顶点覆盖的大小不一定等于两个部分集合中较小的大小，考虑二分图 \(A = \{a1, a2\}\)，\(B = \{b1, b2\}\) 只有一条边 \((a1, b1)\)，此时最小顶点覆盖可以是 \(\{a1\}\) 或 \(\{b1\}\)，大小为 \(1 \neq min(|A|, |B|) = 2\)，故 \(\textnormal{A}\) 表述错误

对于任意顶点覆盖 \(C\) 和任意匹配 \(M\)，由于覆盖 \(M\) 中的所有边需要至少 \(|M|\) 个顶点（因为匹配的边没有公共顶点），因此 \(|C| ≥ |M|\)，故 \(\textnormal{B}\) 表述正确

根据 Kőnig 定理，在二分图中，最大匹配的大小等于最小顶点覆盖的大小，即 \(|C| = |M|\)，故 \(\textnormal{C}\) 表述正确

综上，答案为 \(\textnormal{A}\)

综合

Assume \(\text{P} \neq \text{NP}\), please identify the false statement.

\(\textnormal{A}\). In the minimum-degree spanning problem, we are given a graph \(G=(V, E)\) and wish to find a spanning tree \(T\) of \(G\) so as to minimize the maximum degree of nodes in \(T\). Then it is NP-complete to decide whether or not a given graph has minimum-degree spanning tree of maximum degree two.

\(\textnormal{B}\). There cannot exist a ρ-approximation algorithm for bin packing problem for any \(ρ < 3/2\).

\(\textnormal{C}\). In the minimum-degree spanning problem, we are given a graph \(G=(V, E)\) and wish to find a spanning tree \(T\) of \(G\) so as to minimize the maximum degree of nodes in \(T\). Then there exists an algorithm with approximation ratio less than \(3/2\).

\(\textnormal{D}\). In the knapsack problem, for any given real number \(ε > 0\), there exists an algorithm with approximation ratio less than \(1 + ε\).

答案

判断一个图是否具有最大度为 \(2\) 的最小度生成树，等价于判断图中是否存在哈密顿路径，而哈密顿路径问题是 NP 完全的，故 \(\textnormal{A}\) 陈述正确

装箱问题中，除非 \(\text{P} = \text{NP}\)，否则不存在近似比小于 \(3/2\) 的多项式时间近似算法，故 \(\textnormal{B}\) 陈述正确

最小度生成树问题中，若存在近似比小于 \(3/2\) 的多项式时间算法，则当最优值为 \(2\) 时，算法必须总输出最大度为 \(2\) 的生成树，但这将解决哈密顿路径问题，与 \(\text{P} \neq \text{NP}\) 矛盾，故 \(\textnormal{C}\) 陈述错误。

背包问题存在完全多项式时间近似方案（FPTAS），对于任意 \(ε>0\)，可设计近似比小于 \(1+ε\) 的算法，故 \(\textnormal{D}\) 陈述正确

综上，答案为 \(\textnormal{C}\)

归约？

Which one of the following statements is FALSE?

\(\textnormal{A}\). A language \(L_1\) is polynomial time transformable to \(L_2\) if there exists a polynomial time function \(f\) such that \(w \in L_1\) if \(f(w) \in L_2\).

\(\textnormal{B}\). \(L_1 \leq_p L_2\) and \(L_2 \leq_p L_3\) then \(L_1 \leq_p L_3\).

\(\textnormal{C}\). If \(L_1 \in P\) then \(L_1 \subseteq NP \cap co-NP\).

\(\textnormal{D}\). If language \(L_1\) has a polynomial reduction to language \(L_2\), then the complement of \(L_1\) has a polynomial reduction to the complement of \(L_2\).

答案

在多项式时间归约的标准定义中，要求存在多项式时间可计算函数 \(f\)，使得对于所有字符串 \(w\)，\(w \in L_1\) 当且仅当 \(f(w) \in L_2\)。而选项A仅给出了一个方向（“if”），缺少了“only if”部分，因此定义不完整，无法构成有效的归约，答案为 \(\textnormal{A}\)

Vertex Cover Problem

In the vertex cover problem, if the given graph is a tree, then we can find the optimal solution in polynomial time.

答案

\(\textnormal{T}\)