In computability theory here is what the padding lemma says :

Every partial recursive function $\phi_x$ has $\beth_0$ indices and for each $x$ we can find effectively an infinite set $C_x$ of indices for the same partial recursive function.

In computational complexity theory, the padding argument is a tool which helps to prove that if two complexity classes are equal then some other bigger classes are also equal. In general, this argument consists in adding enough symbols in a langage $L$.

Moreover, in the proof of the padding lemma we consider the Turing program $P_x$ associated with $\phi_x$ consisting in $n$ steps. Then we add an arbitrary number of steps and get a new Turing program which enumerates differently.

Thanks in advance !

  • $\begingroup$ Beyond the name (and the fact that some "padding" is added) I cannot see any deeper connection. For the lemma, I think you add some useless steps after the real computation is done. These are independent of the computation that has been done before (like "move one right and copme back"). In the complexity arguments the padding must depend very much on the 'original' part of the input in order to grow with the complexity of the latter. $\endgroup$ Nov 8, 2021 at 11:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.