GCD is easy. Factoring is comparatively hard, though there are algorithms much better than brute force.
I would have said that complexity theory is the place where we often have simple descriptions of hard- or impossible- to compute values. The busy-beaver function, say.
GCD is easy. Factoring is comparatively hard, though there are algorithms much better than brute force.
I would have said that complexity theory is the place where we often have simple descriptions of hard- or impossible- to compute values. The busy-beaver function, say.
Busy beaver is a little wordy to state in 10 seconds, but is nonetheless a good example.
(And my example in OP has been revised in light of this oversight.)