19 NP Complete

Question 1

Intractable Problems

Answer 1

As they grow larger, we are unable to solve them in reasonable time. (Polynomial time)

Question 2

NP-Complete

Answer 2

No one has yet proven that polynomial time algorith does not exist.

That is in NP and NP-Hard.
(The “hardest” problems in NP)

Question 3

P

Answer 3

The class of decision problems that are solvable in polynomial time.

Question 4

NP

Answer 4

Non-deterministic Polynomial.

The class of decision problems that can be verified in polynomial time by a nondeterminstic algorithm

Question 5

NP-Hard Problems

Answer 5

Are at least as hard as the hardest problems in NP.

Question 6

Relationship between NP-Complete and NP-Hard

Answer 6

All NP-Complete are also NP-Hard

Not all NP-Hard are in NP (despite have NP as a prefix), so a problem can be NP-hard without being NP-complete.

Question 7

Relationship between P and NP

Answer 7

P: Can be solved quickly.

NP: Can be verified quickly, but not solved quickly.

Question 8

Examples of NP-Complete Problems

Answer 8

Hamitonian Cycle Problem
Traveling Salesman Problem
Graph Coloring