Simultaneous (poly-time, log-space) lower bounds

AbstractIn this paper we establish a lower bound for the simultaneous complexity of the halting problem for a class of ‘simple programs’, which allow setting variables to constants and if-goto statements. Let HALT(h, k) be the problem: given a simple program Pk with k variables, determine whether Pk halts within nh steps, where n is the length of Pk. We show that the problem HALT(h, k) cannot be solved in time less than n(h−4)2 and space less than 14(k − 17) log2 n by any Turing machine with one storage tape and binary storage symbols