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.

  • $\begingroup$ Can this Wiki article help you a little bit? $\endgroup$
    – Nobody
    Aug 25, 2018 at 14:14
  • $\begingroup$ 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. $\endgroup$ Aug 25, 2018 at 14:36
  • $\begingroup$ I'm not sure that "how do I phrase this concisely in Croatian?" is on-topic here. $\endgroup$
    – D.W.
    Aug 25, 2018 at 15:09
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 25, 2018 at 15:12

1 Answer 1


I doubt that “overhead” is a term. Here’s what we use in Russian papers:

  1. оверхед — direct transliteration (for informal texts)
  2. издержки — costs (of production)
  3. Translations of “slowdown” (for time) and “blow-up” (for space).

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.