知识卡片

普通读书笔记卡 · 3714.a

相近问题可有不同复杂度

理解等级:中级

书中对比最短路与最长简单路、欧拉回路与哈密顿环、2-CNF与3-CNF可满足性:表面相近不保证复杂度相同。判定问题的约束细节会改变已知复杂度类别,不能只按题目名称类比。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[0,5000))。 - 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与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