关于NP完全问题的2个直观理解 ·什么是NP完全问题： ·在多项式时间内可以“verifiable”的问题 ·什么是verifiable? ·给定一个certification,比如3SAT问题的一个变元赋值，验算其是否是可满足的！ ·为什么优化问题不能直接用NP完全性来考察？ ·比如最短哈密尔顿回路？ ·任意给一个certification,无法断定其是否最短！ ·但是有不少优化问题是“很难”的，怎么办？ ·优化问题和判定问题的“转化”定义 ·优化问题对应的判定问题“很难”=》优化问题也“很难”关于NP完全问题的2个直观理解 • 什么是NP完全问题： • 在多项式时间内可以“verifiable”的问题 • 什么是verifiable？ • 给定一个certification，比如3SAT问题的一个变元赋值，验算其是否是可满足的！ • 为什么优化问题不能直接用NP完全性来考察？ • 比如最短哈密尔顿回路？ • 任意给一个certification，无法断定其是否最短！ • 但是有不少优化问题是“很难”的，怎么办？ • 优化问题和判定问题的“转化”定义 • 优化问题对应的判定问题“很难”=》优化问题也“很难