Computational complexity describes resource requirements such as running time and memory as functions of input size. It helps distinguish methods whose costs grow moderately from those that become impractical rapidly, even when a small example runs quickly.
The difficulty of finding a solution can differ from the difficulty of checking one. Complexity results describe carefully specified problems and computational assumptions; they do not automatically establish the speed of a practical implementation or show that an AI system can efficiently solve every difficult task.
ELI5
Imagine arranging deliveries among a few addresses. Trying every possible order is manageable for a tiny list, but the number of possible routes grows very quickly as more addresses are added.
Computational complexity asks how much harder the job becomes when the list gets bigger. It also distinguishes finding a good route from checking the length of a route somebody already supplied.
Does complexity measure one program's exact speed?
It usually describes how resource use grows with input size. Hardware, implementation details and the particular input also affect actual running time.
Is checking a solution always as hard as finding it?
No. For some problem classes a proposed solution can be checked efficiently even when no efficient general method for finding a solution is known.
