知识卡片
相近问题可有不同复杂度
书中对比最短路与最长简单路、欧拉回路与哈密顿环、2-CNF与3-CNF可满足性:表面相近不保证复杂度相同。判定问题的约束细节会改变已知复杂度类别,不能只按题目名称类比。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Several NP-complete problems are particularly tantalizing because they seem on the surface to be similar to problems that we know how to solve in polynomial time. In each of the following pairs of problems, one is solvable in polynomial time and the other is NP-complete, but the difference between the problems appears to be slight: Shortest versus longest simple paths: In Chapter 22, we saw that even with negative edge weights, we can find shortest paths from a single source in a directed graph G = (V, E) in O(VE) time. Finding a longest simple path between two vertices is difficult, however. Merely determining whether a graph contains a simple path with at least a given number of edges is NP-complete. Euler tour versus hamiltonian cycle: An Euler tour of a strongly connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it is allowed to visit each vertex more than once. Problem 20-3 on page 583 asks you to show how to determine whether a strongly connected, directed graph has an