Introduction

Within the branch of Mathematics which deals with the theory of computation, we find an interesting intersection of computer science and mathematics called Computational Complexity Theory, which is concerned with the analysis and classification of computational problems according to the inherent difficulty of the computational problem. Two of the computational classes of classification used by Computational Complexity Theory are the NP classification, Non-deterministic Polynomial Time, and the P classification, Polynomial Time.

NP-Complete is a subset of the NP class, and refers to the set of all decision problems whose solutions can be verified in polynomial time. The reason this subclass is of interest to computer scientists is studied is because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve that problem (P).

P=NP Problem

A famous unsolved problem in computer science

Exercises

Continue to the next section