Problem 4 - NP-Completeness

Answer the following questions concerning computational complexity.

1.

Describe the definition of NP-completness.

2.

Describe an outline of NP-completness of the satisfiability problem of a logical formula in the CNF form.

3.

By applying the theory of NP-completeness, discuss approximation algorithms and their goodness in respect to approximate solutions.

See [HOP79] and [AHO83] for a detailed answer.