Now showing items 1-1 of 1

    • On Time Versus Space 

      Hopcroft, John E.; Paul, Wolfgang J.; Valiant, Leslie (Cornell University, 1975-12)
      It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Consequently, for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity ...