Turing machine space complexity is related to circuit depth complexity. The relationship complements the known connection between Turing machine time and circuit size, thus enabling us to expose the related nature of some important open problems concerning Turing machine and circuit complexity. We are also able to show some connection between Turing machine complexity and arithmetic complexity.
No takes yet. Share an insight, caveat, or question.
Allan Borodin (1977) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: