I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as;

'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

The paper I am writing is in Croatian where I cannot find a properly convenient word like "overhead". Also, I am unable to find a strict Computer Science definition for the term.

Specifically, I have $Time(M)$ as the cost of reducing the $\lambda$-term $M$ to its normal form and a Turing machine able to simulate this reduction in $O((Time(M))^4)$. Therefore, I would like to say "this TM can simulate $\lambda$-calculus with polynomial-time [overhead]" concisely as it is in English.

I would appreciate any suggestion in the form of literature references for the definition, advice on how to best define it myself or even synonyms of the word.

• Can this Wiki article help you a little bit? – scaaahu Aug 25 '18 at 14:14
• Thanks. Your suggestion also gives me an idea to narrow my question. It is not that I'm unsure what overhead is, but the problem I have is how to say it concisely in Croatian. I may have to define a new word in my paper or just use "overhead", but I will wait for more suggestions. – Sandro Lovnički Aug 25 '18 at 14:36
• I'm not sure that "how do I phrase this concisely in Croatian?" is on-topic here. – D.W. Aug 25 '18 at 15:09
• You are right and I am not asking that. I am asking for various definitions or possible synonyms for overhead to help me with phrasing it. Because, where else could I find a group of people capable of correctly rephrasing polynomial-time overhead when simulating computation machines. – Sandro Lovnički Aug 25 '18 at 15:12