Easy to Verify Does Not Mean Easy to Solve: LLMs and the P vs NP Problem

A popular claim in AI circles suggests that if a problem is easy to verify, then an AI can easily learn to solve it — but this conflates verification complexity with learning complexity. In computer science, NP problems are those whose solutions can be verified in polynomial time, while P problems can be solved in polynomial time; whether P equals NP remains unsolved. Verification does help AI training by providing feedback signals — as seen in code generation and formal math proofs where unit tests and proof checkers enable rapid progress. However, verifiers often produce sparse binary signals, and finding a valid solution can still require exponential search even when checking it takes linear time. The more accurate principle is that AI can approximate solutions when dense training signals can be extracted from a verifier, but this is a probabilistic heuristic, not a proof that P equals NP.