Theorem. Weak HCH (and similar proposals) contain EXP.
Proof sketch: I give a strategy that H can follow to determine whether some machine that runs in O(2cnk) time accepts. Basically, we need to answer questions of the form “Does cell x have value y at time t.” and “Was the head in position x at time t?”, where x and t are bounded by some function in O(2cnk). Using place-system representations of x and t, these questions have length in O(nk), so they can be asked. Further, each question is a simple function of a constant number of other such questions about earlier times as long as t>0, and can be answered directly in the base case t=0.
Yeah, I think that’s absolutely right—I actually already have a version of my market making EXP proof for amplification that I’ve been working on cleaning up for publishing. But regardless of how you prove it I certainly agree that I understated amplification here and that it can in fact get to EXP.
Theorem. Weak HCH (and similar proposals) contain EXP.
Proof sketch: I give a strategy that H can follow to determine whether some machine that runs in O(2cnk) time accepts. Basically, we need to answer questions of the form “Does cell x have value y at time t.” and “Was the head in position x at time t?”, where x and t are bounded by some function in O(2cnk). Using place-system representations of x and t, these questions have length in O(nk), so they can be asked. Further, each question is a simple function of a constant number of other such questions about earlier times as long as t>0, and can be answered directly in the base case t=0.
Yeah, I think that’s absolutely right—I actually already have a version of my market making EXP proof for amplification that I’ve been working on cleaning up for publishing. But regardless of how you prove it I certainly agree that I understated amplification here and that it can in fact get to EXP.