Explaining computational complexity theory?

Question

Assuming some background in mathematics, how would you give a general overview of computational complexity theory to the naive? I am looking for an explanation of the P = NP question. What is P? What is NP? What is a NP-Hard?

Answer 1

NP means nondeterministic polynomial time, which is referring to a class of decisions problems that cannot be solve within polynomial time with regard to the input. Usually speaking, a NP problem have two parts: solve and verify. The solve part cannot be solve under polynomial time (require brute force, exponential approach), but once we obtain a possible solution, we can verify it in polynomial time of the input. The set of NP contains P.

When speaking about NP and NP-hard, we also talk about NP-complete. NP-complete are NP problems that have a verifier in polynomial time and cannot be done. A problem is NP-complete if all other NP problems can be reduced to it in polynomial time.

NP-hard means that the problem is known to be as hard as the hardest problem in NP-complete. The formal definition for a problem to be NP-hard is that if every other problem in NP-complete can be reduced to it. Usually speaking we show a problem to be NP-hard by showing that it can be reduced from another known NP-hard problem.

So P is a subset of NP. The intersection of NP and NP-hard is NP-complete.

The problem is whether P = NP, and it is currently unsolvable. We are hoping that this can be provable as False.