Great question. I don’t have a satisfying answer. Perhaps a cynical answer is survival bias—we remember the asymptotic results that eventually become relevant (because people develop practical algorithms or a deeper theory is discovered) but don’t remember the irrelevant ones.
Existence results are categorically easier to prove than explicit algorithms. Indeed, classical existence may hold (the former) while intuitioinistically (the latter) might not. We would expect non-explicit existence results to appear before explicit algorithms.
One minor remark on ‘quantifying over all boolean algorithms’. Unease with quantification over large domains may be a vestige of set-theoretic thinking that imagines types as (platonic) boxes. But a term of a for-all quantifier is better thought of as an algorithm/ method to check the property for any given term (in this case a Boolean circuit). This doesn’t sound divorced from practice to my ears.
Great question. I don’t have a satisfying answer. Perhaps a cynical answer is survival bias—we remember the asymptotic results that eventually become relevant (because people develop practical algorithms or a deeper theory is discovered) but don’t remember the irrelevant ones.
Existence results are categorically easier to prove than explicit algorithms. Indeed, classical existence may hold (the former) while intuitioinistically (the latter) might not. We would expect non-explicit existence results to appear before explicit algorithms.
One minor remark on ‘quantifying over all boolean algorithms’. Unease with quantification over large domains may be a vestige of set-theoretic thinking that imagines types as (platonic) boxes. But a term of a for-all quantifier is better thought of as an algorithm/ method to check the property for any given term (in this case a Boolean circuit). This doesn’t sound divorced from practice to my ears.