I recall hearing about a result, or maybe a cluster of results, in some area of complexity theory, probably algebraic, to the effect that there are known, specific, short formulas whose minimal derivation is known to be exceedingly long. Or perhaps it is a specific function that requires an exceedingly deep curcuit. The "philosophy" seemed to be that such examples would threaten to make the older asymptotic question obsolete: "Who cares about asymptotics if the constants are huge." Can anyone, given these hints, describe ( and direct me to) the result I overheard?



nonasymptotic complexity results
Perhaps you were told about



> 
> Larry J. Stockmeyer, Albert R. Meyer: Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM 49(6): 753-784 (2002)
> 
> 
> 


From the abstract: *"An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In particular, to decide the truth of logical formulas of length at most 610 in this second-order language requires a circuit containing at least $10^{125}$ gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe.*


This demonstrates a specific function for which all inputs of size 610 cannot be determined within the physical universe. The proof is essentially a diagonalization argument, but is very carefully executed to take all constants into account.


(Note this is actually based on an asymptotic result, but it took some work to get a concrete lower bound out of it.)


