LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 373-375 of 486

    • 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 & ...

    • Bicontinuous Extensions of Invertible Combinatorial Functions 

      Toffoli, Tommaso (1979-01)
      We discuss and solve the problem of constructing a diffeomorphic componentwise extension for an arbitrary invertible combinatorial function. Interpreted in physical terms, our solution constitutes a proof of the physical ...

    • An Improved Proof of the Rabin-Harmanis-Stearns Conjecture 

      Perry, Harold M. (1979-01)
      We offer an improved presentation of Aanderaa's constructive proof of the Rabin-Hartmanis-Stearns conjecture: For all k≥2, there exists a language Lk such that Lk can be recoginzed by a k-worktape real time Turing machine ...