Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:jeanpaul:section2 [2012/01/15 00:32] – mugabej | courses:cs211:winter2012:journals:jeanpaul:section2 [2012/01/17 05:02] (current) – mugabej | ||
|---|---|---|---|
| Line 59: | Line 59: | ||
| * Suppose that player P2 has a target bound B and we want to know if there is a strategy for P2 such that no matter how P1 plays,P2 will be able to select a set of nodes with a total value of at least B. This is an instance of the // | * Suppose that player P2 has a target bound B and we want to know if there is a strategy for P2 such that no matter how P1 plays,P2 will be able to select a set of nodes with a total value of at least B. This is an instance of the // | ||
| \\ | \\ | ||
| - | Not only is it computationally difficult to determine whether a player has a winning strategy, on a reasonably sized graph, it would be hard to be convinced that a player has a winning strategy. The // | + | Not only is it computationally difficult to determine whether a player has a winning strategy, on a reasonably sized graph, it would be hard to be convinced that a player has a winning strategy. The // |
| - | // | + | \\ |
| + | |||
| + | Motivations for discussing the five representative problems is obvious: They will serve as reference as we solve problems relating to algorithms. They simply form a reference for other problems. The question I have though is: "Do these problems represent all of the problems we can ever encounter when dealing with algorithm analysis or they serve as reference for most of the problems?" | ||
| + | |||
| + | I want to remember the difference between NP-complete and PSPACE-complete problems: For NP-complete, | ||
| + | |||
| + | Since this section was straightforward, | ||
