Category	P	NP	NP-complete	NP-hard
Definition	Problems that can be solved in polynomial time by a deterministic algorithm.	Problems whose solutions can be verified in polynomial time by a deterministic algorithm.	Problems that are both in NP and as hard as the hardest problems in NP (NP-hard and in NP).	Problems as hard as NP-complete problems but not necessarily in NP (not required to be verifiable in polynomial time).
Key Characteristics	Efficiently solvable in polynomial time.	Solution verification is efficient (polynomial time).	If any NP-complete problem is solved in polynomial time, all NP problems can be solved in polynomial time.	May not even be solvable or verifiable in polynomial time.
	Verifiable and solvable in polynomial time.	Includes all problems in P.	Requires verification and reduction properties.	Includes optimization problems and undecidable problems.
	A subset of NP problems.	May not be efficiently solvable.	Solving one in polynomial time solves all NP problems in polynomial time.	Not necessarily solvable or verifiable in polynomial time.
Examples	Sorting (e.g., Merge Sort), Searching	Boolean Satisfiability (SAT), Graph Coloring	3-SAT, Traveling Salesman (decision version)	Halting Problem, Bin Packing Problem

Problem Solving:
- P: Problems can be both solved and verified in polynomial time.
- NP: Problems may not be solved in polynomial time but can be verified in polynomial time.
- NP-complete: Problems are the hardest in NP and are solvable if any NP problem is solved in polynomial time.
- NP-hard: Problems are as hard as NP-complete but not necessarily in NP (i.e., they might not even have a verifiable solution in polynomial time).
Inclusion:
- P: Subset of NP.
- NP-complete: Subset of NP-hard.
- NP-hard: Not necessarily a subset of NP.
Implication:
- Solving any NP-complete problem in polynomial time implies P=NP.
- Solving an NP-hard problem does not necessarily affect P=NP, as NP-hard problems might not be verifiable.

Key differences between P, NP, NP-complete, and NP-hard