A decision problem X is in the class P if:
Class P consists of all decision problems solvable by a deterministic algorithm in polynomial time O($n^k)$ for some constant k.
A decision problem X is in the class NP if:
Class NP consists of decision problems for which a given solution certificate can be checked (verified) for validity in polynomial time.
A decision problem X is NP-COMPLETE if:
A problem X is NP-Complete if both conditions hold: (1) X is in NP, and (2) X is NP-Hard (every problem in NP reduces to X in polynomial time).
What is the famous COOK-LEVIN THEOREM statement?
The Cook-Levin Theorem (1971) proved that SAT (Boolean Satisfiability) is NP-Complete, establishing the foundation of NP-completeness theory.
If a problem A is polynomial-time reducible to problem B (A <=_p B), and problem A is NP-Hard, then problem B is:
Polynomial reduction A <=_p B means B is at least as hard as A. Since A is NP-Hard, B must also be NP-Hard.