= 27d567bc2d48d9f40e9ccc20ea370b15)
asr comments on Where Fermi Fails: What is hard to estimate? - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (46)
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.)