Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Algorithm design - Chapter 8: Intractability II

Lecture Algorithm design - Chapter 8 "Intractability II" include all of the following: Decision problems, definition of P, certifiers and certificates: composite, certifiers and certificates: 3-satisfiability, certifiers and certificates: Hamilton path, definition of NP,.and another content. | 8. Intractability II P vs. NP NP-complete co-NP NP-hard Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley Copyright 2013 Kevin Wayne http www.cs.princeton.edu wayne kleinberg-tardos Last updated on Sep 8 2013 6 41 AM Recap Vertex-Cover Ham-Cycle Planar-3-Color Scheduling Set-Cover 3-Sat poly-time reduces to all of these problems and many many more 2 P vs. NP Section 8.3 8. Intractability .