我正在学习P、NP和NP-完全问题,遇到了一些问题。
如果可以在多项式时间内解决一个问题,那么它是P问题;如果可以在多项式时间内验证一个问题,那么它是NP问题。我也明白,如果一个问题既是NP问题,又可以从现有的NP-完全问题中规约得到,那么它就是NP-完全问题。
我知道SAT、3-SAT、Independent Set、Vertex Cover、Hamiltonian Cycle、Subset Sum和Traveling Salesman都是NP-完全问题。但是,我遇到了一个问题,被告知在一个图中确定是否存在5个顶点的独立集是多项式时间可解的,而不是NP-完全的。这让我感到困惑,因为我认为独立集问题是NP-完全问题。
那么,在哪些情况下这些“NP-完全”问题不是NP-完全问题,而是P问题呢?当给定一个问题时,如何确定它是P问题还是NP-完全问题?如果问题确实有多项式时间可解的解决方案,而我无法想出来,因此走了NP-完全的路线,那么我如何知道自己犯了错误?
如果可以在多项式时间内解决一个问题,那么它是P问题;如果可以在多项式时间内验证一个问题,那么它是NP问题。我也明白,如果一个问题既是NP问题,又可以从现有的NP-完全问题中规约得到,那么它就是NP-完全问题。
我知道SAT、3-SAT、Independent Set、Vertex Cover、Hamiltonian Cycle、Subset Sum和Traveling Salesman都是NP-完全问题。但是,我遇到了一个问题,被告知在一个图中确定是否存在5个顶点的独立集是多项式时间可解的,而不是NP-完全的。这让我感到困惑,因为我认为独立集问题是NP-完全问题。
那么,在哪些情况下这些“NP-完全”问题不是NP-完全问题,而是P问题呢?当给定一个问题时,如何确定它是P问题还是NP-完全问题?如果问题确实有多项式时间可解的解决方案,而我无法想出来,因此走了NP-完全的路线,那么我如何知道自己犯了错误?