computer science//complexity theory

Complexity theory is the branch of computer science that measures how many resources (time, space, randomness) a problem requires to solve, and it tells how hard a problem is once it is known to be solvable.

Complexity theory is the branch of computer science that measures how many resources (time, space, randomness) a problem requires to solve, and it tells how hard a problem is once it is known to be solvable.

It organizes problems into complexity classes: P (polynomial time), NP (verifiable in polynomial time), PSPACE (polynomial space), EXPTIME, and many others.

The P vs NP question is the central open problem: can every problem whose solution is efficiently verifiable also be efficiently solved? The answer is widely believed to be no, and it has stayed unproven since 1971.

A reduction proves that problem A is at least as hard as problem B by showing that solving A would solve B. This is how PSPACE-completeness is established.

In ML, training a neural network is NP-hard in the worst case, but gradient descent finds good-enough solutions in practice. The loss landscape of real problems is friendlier than worst-case theory predicts.

Compositionality connects complexity to extended thinking: chain-of-thought gives the model polynomial scratch space (the context window), enabling it to tackle problems that would require exponential search in a single forward pass.