Browsing LCS Technical Memos (1974 - 2003) by Author "Adleman, Leonard M."

Now showing items 1-2 of 2

    • Metal Poker 

      Shamir, Adi; Rivest, Ronald L.; Adleman, Leonard M. (1979-02)
      Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over the phone)? This paper provides the following answers: 1. No. (Rigorous mathematical proof supplied. 2. Yes. (Correct & ...

    • Space-Bounded Simulation of Multitape Turing Machines 

      Adleman, Leonard M.; Loui, Michael C. (1980-01)
      A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: every deterministic multitape Turing machine of time complexity T(n) can be simulated by a deterministic Turing machine of space complexity T(n)/log ...