CHAPTER

8

Nondeterministic

Algorithms

PREREQUISITES

Before beginning this chapter, you should be able to

• Write and explain an algorithm


• Describe growth rates and order

GOALS

At the end of this chapter, you should be able to

• Define class P, class NP, and NP-complete


• Explain the difference between decision and optimization problems


• Describe the classic NP problems and why they are important


• Describe what puts a problem into class NP


• Describe why P ⊆ NP


• Explain why “P = NP?” is still an open question


• Write an algorithm to check a potential solution to an NP problem

STUDY SUGGESTIONS

As you are working through the chapter, you should rework the examples to

make sure you understand them. You should specifically trace through the

algorithms and input data presented to try to recreate the “results” given. You

should also try to answer any questions before reading on. A hint or the answer

is in the sentences following the question.