## Computer Science GRE Study Guide, Computational complexity, including NP-completeness

Table of Contents III. Theory and Mathematical Background – 40% A. Algorithms and complexity 4. Computational complexity, including NP-completeness a. Definition: Computability refers to whether or not a certain type of machine can solve a certain problem. b. Definition: NP-complete problems are special problems in modern computing. The name comes from the fact that you