Sipser: Section 7.5
From CSWiki
CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_7
Contents |
[edit]
Additional NP-Complete Problem
[edit]
Summary
Sipser further proves that some of the previously discussed NP problems are NP-Complete. The strategy is finding a polynomial time reduction from 3SAT problem to the problem we want to prove to be NP-Complete.
[edit]
More NP-Complete Problems
[edit]
CLIQUE
(page 283)
[edit]
VERTEX-COVER
(page 284)
[edit]
HAMPATH
(page 286)
CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_7
